code: 
  
  
  '''simple docstring'''
  
  
  
  from __future__ import annotations
  
  import unittest
  from collections.abc import Iterator
  
  
  
  
  
  class 							__UpperCamelCase       :
  
  
  
  
  	def __init__(     self		,       __a		,       __a							):
  
  						'''simple docstring'''
  
  
  
  
  
  						__a    : int      					=						label
  						__a    : Optional[Any]      					=						parent
  						__a    : Union[str, Any]      					=						None
  						__a    : Tuple      					=						None
  
  
  
  
  
  class 							__UpperCamelCase       :
  
  
  
  
  	def __init__(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						__a    : Dict      					=						None
  
  
  
  
  	def    __UpperCAmelCase							(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						__a    : List[Any]      					=						None
  
  
  
  
  	def    __UpperCAmelCase							(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						return self.root is None
  
  
  
  
  	def    __UpperCAmelCase							(     self		,       __a							):
  
  						'''simple docstring'''
  
  
  
  
  
  						__a    : Optional[Any]      					=						self._put(self.root		,       a_							)
  
  
  
  
  	def    __UpperCAmelCase							(     self		,       __a		,       __a		,       __a = None							):
  
  						'''simple docstring'''
  
  
  
  
  
  						if node is None:
  											__a    : Optional[int]      					=						Node(a_		,       a_							)
  						else:
  											if label < node.label:
  																__a    : List[Any]      					=						self._put(node.left		,       a_		,       a_							)
  											elif label > node.label:
  																__a    : Union[str, Any]      					=						self._put(node.right		,       a_		,       a_							)
  											else:
  																__a    : List[str]      					=						f"""Node with label {label} already exists"""
  																raise Exception(a_							)
  
  						return node
  
  
  
  
  	def    __UpperCAmelCase							(     self		,       __a							):
  
  						'''simple docstring'''
  
  
  
  
  
  						return self._search(self.root		,       a_							)
  
  
  
  
  	def    __UpperCAmelCase							(     self		,       __a		,       __a							):
  
  						'''simple docstring'''
  
  
  
  
  
  						if node is None:
  											__a    : Optional[Any]      					=						f"""Node with label {label} does not exist"""
  											raise Exception(a_							)
  						else:
  											if label < node.label:
  																__a    : Optional[Any]      					=						self._search(node.left		,       a_							)
  											elif label > node.label:
  																__a    : str      					=						self._search(node.right		,       a_							)
  
  						return node
  
  
  
  
  	def    __UpperCAmelCase							(     self		,       __a							):
  
  						'''simple docstring'''
  
  
  
  
  
  						__a    : str      					=						self.search(a_							)
  						if node.right and node.left:
  											__a    : int      					=						self._get_lowest_node(node.right							)
  											__a    : List[str]      					=						node.left
  											__a    : Optional[int]      					=						node.right
  											__a    : Union[str, Any]      					=						lowest_node
  											if node.right:
  																__a    : Optional[int]      					=						lowest_node
  											self._reassign_nodes(a_		,       a_							)
  						elif not node.right and node.left:
  											self._reassign_nodes(a_		,       node.left							)
  						elif node.right and not node.left:
  											self._reassign_nodes(a_		,       node.right							)
  						else:
  											self._reassign_nodes(a_		,       a_							)
  
  
  
  
  	def    __UpperCAmelCase							(     self		,       __a		,       __a							):
  
  						'''simple docstring'''
  
  
  
  
  
  						if new_children:
  											__a    : Any      					=						node.parent
  
  						if node.parent:
  											if node.parent.right == node:
  																__a    : List[str]      					=						new_children
  											else:
  																__a    : int      					=						new_children
  						else:
  											__a    : int      					=						new_children
  
  
  
  
  	def    __UpperCAmelCase							(     self		,       __a							):
  
  						'''simple docstring'''
  
  
  
  
  
  						if node.left:
  											__a    : Dict      					=						self._get_lowest_node(node.left							)
  						else:
  											__a    : int      					=						node
  											self._reassign_nodes(a_		,       node.right							)
  
  						return lowest_node
  
  
  
  
  	def    __UpperCAmelCase							(     self		,       __a							):
  
  						'''simple docstring'''
  
  
  
  
  
  						try:
  											self.search(a_							)
  											return True
  						except Exception:
  											return False
  
  
  
  
  	def    __UpperCAmelCase							(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						if self.root is None:
  											raise Exception('Binary search tree is empty'							)
  
  						__a    : Optional[int]      					=						self.root
  						while node.right is not None:
  											__a    : Tuple      					=						node.right
  
  						return node.label
  
  
  
  
  	def    __UpperCAmelCase							(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						if self.root is None:
  											raise Exception('Binary search tree is empty'							)
  
  						__a    : Optional[Any]      					=						self.root
  						while node.left is not None:
  											__a    : int      					=						node.left
  
  						return node.label
  
  
  
  
  	def    __UpperCAmelCase							(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						return self._inorder_traversal(self.root							)
  
  
  
  
  	def    __UpperCAmelCase							(     self		,       __a							):
  
  						'''simple docstring'''
  
  
  
  
  
  						if node is not None:
  											yield from self._inorder_traversal(node.left							)
  											yield node
  											yield from self._inorder_traversal(node.right							)
  
  
  
  
  	def    __UpperCAmelCase							(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						return self._preorder_traversal(self.root							)
  
  
  
  
  
  	def    __UpperCAmelCase							(     self		,       __a							):
  
  						'''simple docstring'''
  
  
  
  
  
  						if node is not None:
  											yield node
  											yield from self._preorder_traversal(node.left							)
  											yield from self._preorder_traversal(node.right							)
  
  
  
  
  
  class 							__UpperCamelCase       (	unittest.TestCase      ):
  
  
  
  
  	@staticmethod
  	def    __UpperCAmelCase							(     ):
  
  						'''simple docstring'''
  
  
  
  
  
  						__a    : str      					=						BinarySearchTree()
  						t.put(8							)
  						t.put(3							)
  						t.put(6							)
  						t.put(1							)
  						t.put(10							)
  						t.put(14							)
  						t.put(13							)
  						t.put(4							)
  						t.put(7							)
  						t.put(5							)
  
  						return t
  
  
  
  
  	def    __UpperCAmelCase							(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						__a    : List[Any]      					=						BinarySearchTree()
  						assert t.is_empty()
  
  						t.put(8							)
  						assert t.root is not None
  						assert t.root.parent is None
  						assert t.root.label == 8
  
  						t.put(10							)
  						assert t.root.right is not None
  						assert t.root.right.parent == t.root
  						assert t.root.right.label == 10
  
  						t.put(3							)
  						assert t.root.left is not None
  						assert t.root.left.parent == t.root
  						assert t.root.left.label == 3
  
  						t.put(6							)
  						assert t.root.left.right is not None
  						assert t.root.left.right.parent == t.root.left
  						assert t.root.left.right.label == 6
  
  						t.put(1							)
  						assert t.root.left.left is not None
  						assert t.root.left.left.parent == t.root.left
  						assert t.root.left.left.label == 1
  
  						with self.assertRaises(a_							):  # noqa: B017
  											t.put(1							)
  
  
  
  
  	def    __UpperCAmelCase							(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						__a    : Any      					=						self._get_binary_search_tree()
  
  						__a    : Dict      					=						t.search(6							)
  						assert node.label == 6
  
  						__a    : str      					=						t.search(13							)
  						assert node.label == 13
  
  						with self.assertRaises(a_							):  # noqa: B017
  											t.search(2							)
  
  
  
  
  	def    __UpperCAmelCase							(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						__a    : Union[str, Any]      					=						self._get_binary_search_tree()
  
  						t.remove(13							)
  						assert t.root is not None
  						assert t.root.right is not None
  						assert t.root.right.right is not None
  						assert t.root.right.right.right is None
  						assert t.root.right.right.left is None
  
  						t.remove(7							)
  						assert t.root.left is not None
  						assert t.root.left.right is not None
  						assert t.root.left.right.left is not None
  						assert t.root.left.right.right is None
  						assert t.root.left.right.left.label == 4
  
  						t.remove(6							)
  						assert t.root.left.left is not None
  						assert t.root.left.right.right is not None
  						assert t.root.left.left.label == 1
  						assert t.root.left.right.label == 4
  						assert t.root.left.right.right.label == 5
  						assert t.root.left.right.left is None
  						assert t.root.left.left.parent == t.root.left
  						assert t.root.left.right.parent == t.root.left
  
  						t.remove(3							)
  						assert t.root is not None
  						assert t.root.left.label == 4
  						assert t.root.left.right.label == 5
  						assert t.root.left.left.label == 1
  						assert t.root.left.parent == t.root
  						assert t.root.left.left.parent == t.root.left
  						assert t.root.left.right.parent == t.root.left
  
  						t.remove(4							)
  						assert t.root.left is not None
  						assert t.root.left.left is not None
  						assert t.root.left.label == 5
  						assert t.root.left.right is None
  						assert t.root.left.left.label == 1
  						assert t.root.left.parent == t.root
  						assert t.root.left.left.parent == t.root.left
  
  
  
  
  	def    __UpperCAmelCase							(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						__a    : List[str]      					=						self._get_binary_search_tree()
  
  						t.remove(3							)
  						assert t.root is not None
  						assert t.root.left is not None
  						assert t.root.left.left is not None
  						assert t.root.left.right is not None
  						assert t.root.left.right.left is not None
  						assert t.root.left.right.right is not None
  						assert t.root.left.label == 4
  						assert t.root.left.right.label == 6
  						assert t.root.left.left.label == 1
  						assert t.root.left.right.right.label == 7
  						assert t.root.left.right.left.label == 5
  						assert t.root.left.parent == t.root
  						assert t.root.left.right.parent == t.root.left
  						assert t.root.left.left.parent == t.root.left
  						assert t.root.left.right.left.parent == t.root.left.right
  
  
  
  
  	def    __UpperCAmelCase							(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						__a    : str      					=						self._get_binary_search_tree()
  						t.empty()
  						assert t.root is None
  
  
  
  
  	def    __UpperCAmelCase							(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						__a    : List[str]      					=						self._get_binary_search_tree()
  						assert not t.is_empty()
  
  						t.empty()
  						assert t.is_empty()
  
  
  
  
  	def    __UpperCAmelCase							(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						__a    : Dict      					=						self._get_binary_search_tree()
  
  						assert t.exists(6							)
  						assert not t.exists(-1							)
  
  
  
  
  	def    __UpperCAmelCase							(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						__a    : int      					=						self._get_binary_search_tree()
  
  						assert t.get_max_label() == 14
  
  						t.empty()
  						with self.assertRaises(a_							):  # noqa: B017
  											t.get_max_label()
  
  
  
  
  	def    __UpperCAmelCase							(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						__a    : Optional[int]      					=						self._get_binary_search_tree()
  
  						assert t.get_min_label() == 1
  
  						t.empty()
  						with self.assertRaises(a_							):  # noqa: B017
  											t.get_min_label()
  
  
  
  
  	def    __UpperCAmelCase							(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						__a    : Dict      					=						self._get_binary_search_tree()
  
  						__a    : Any      					=						[i.label for i in t.inorder_traversal()]
  						assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 10, 13, 14]
  
  
  
  
  
  	def    __UpperCAmelCase							(     self							):
  
  						'''simple docstring'''
  
  
  
  
  
  						__a    : Optional[int]      					=						self._get_binary_search_tree()
  
  						__a    : List[str]      					=						[i.label for i in t.preorder_traversal()]
  						assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 10, 14, 13]
  
  
  
  
  
  
  def 						lowerCamelCase							():
  					__a    : Any      					=						BinarySearchTree()
  					t.put(8     )
  					t.put(3     )
  					t.put(6     )
  					t.put(1     )
  					t.put(10     )
  					t.put(14     )
  					t.put(13     )
  					t.put(4     )
  					t.put(7     )
  					t.put(5     )
  
  					print(
  					    '\n            8\n           / \\\n          3   10\n         / \\    \\\n        1   6    14\n           / \\   /\n          4   7 13\n           \\\n            5\n        '     )
  
  					print('Label 6 exists:'		,   t.exists(6     )     )
  					print('Label 13 exists:'		,   t.exists(13     )     )
  					print('Label -1 exists:'		,   t.exists(-1     )     )
  					print('Label 12 exists:'		,   t.exists(12     )     )
  
  					# Prints all the elements of the list in inorder traversal
  					__a    : Union[str, Any]      					=						[i.label for i in t.inorder_traversal()]
  					print('Inorder traversal:'		,   UpperCamelCase__     )
  
  					# Prints all the elements of the list in preorder traversal
  					__a    : Dict      					=						[i.label for i in t.preorder_traversal()]
  					print('Preorder traversal:'		,   UpperCamelCase__     )
  
  					print('Max. label:'		,   t.get_max_label()     )
  					print('Min. label:'		,   t.get_min_label()     )
  
  					# Delete elements
  					print('\nDeleting elements 13, 10, 8, 3, 6, 14'     )
  					print(
  					    '\n          4\n         / \\\n        1   7\n             \\\n              5\n        '     )
  					t.remove(13     )
  					t.remove(10     )
  					t.remove(8     )
  					t.remove(3     )
  					t.remove(6     )
  					t.remove(14     )
  
  					# Prints all the elements of the list in inorder traversal after delete
  					__a    : str      					=						[i.label for i in t.inorder_traversal()]
  					print('Inorder traversal after delete:'		,   UpperCamelCase__     )
  
  					# Prints all the elements of the list in preorder traversal after delete
  					__a    : Tuple      					=						[i.label for i in t.preorder_traversal()]
  					print('Preorder traversal after delete:'		,   UpperCamelCase__     )
  
  					print('Max. label:'		,   t.get_max_label()     )
  					print('Min. label:'		,   t.get_min_label()     )
  
  
  if __name__ == "__main__":
  							binary_search_tree_example()
  
  
  
  
style_context: 
  
  
  '''simple docstring'''
  
  
  
  import itertools
  
  
  
  
  
  
  def 						lowerCamelCase							(_SCREAMING_SNAKE_CASE   :     int = 1_000_000     ):
  					__a    : str      					=						[1]
  
  					for i in itertools.count(len(_SCREAMING_SNAKE_CASE     )     ):
  										__a    : Dict      					=						0
  										for j in itertools.count(1     ):
  															__a    : int      					=						-1 if j % 2 == 0 else +1
  															__a    : Optional[int]      					=						(j * j * 3 - j) // 2
  															if index > i:
  																				break
  															item += partitions[i - index] * sign
  															item %= number
  															index += j
  															if index > i:
  																				break
  															item += partitions[i - index] * sign
  															item %= number
  
  										if item == 0:
  															return i
  										partitions.append(_SCREAMING_SNAKE_CASE     )
  
  					return 0
  
  
  if __name__ == "__main__":
  	import doctest
  
  	doctest.testmod()
  
  	print(f'''{solution() = }''')
  
  
  
  