


'''simple docstring'''



from __future__ import annotations

import unittest
from collections.abc import Iterator



class       a							:


     """simple docstring"""






     def __init__(							self	:						Tuple				,					snake_case	:						int				,					snake_case	:						Node | None     )		->				None:
          __UpperCAmelCase      :					Any    				=     label
          __UpperCAmelCase      :					List[Any]    				=     parent
          __UpperCAmelCase      :					Node | None    				=     None
          __UpperCAmelCase      :					Node | None    				=     None



class       a							:


     """simple docstring"""






     def __init__(							self	:						Optional[int]     )		->				None:
          __UpperCAmelCase      :					Node | None    				=     None

     def 					lowerCamelCase__					(							self	:						Dict     )		->				None:
          __UpperCAmelCase      :					List[Any]    				=     None

     def 					lowerCamelCase__					(							self	:						Tuple     )		->				bool:
          return self.root is None

     def 					lowerCamelCase__					(							self	:						str				,					snake_case	:						int     )		->				None:
          __UpperCAmelCase      :					Union[str, Any]    				=     self._put(self.root				,					snake_case     )

     def 					lowerCamelCase__					(							self	:						Dict				,					snake_case	:						Node | None				,					snake_case	:						int				,					snake_case	:						Node | None = None     )		->				Node:
          if node is None:
               __UpperCAmelCase      :					Optional[int]    				=     Node(snake_case				,					snake_case     )
          else:
               if label < node.label:
                    __UpperCAmelCase      :					List[str]    				=     self._put(node.left				,					snake_case				,					snake_case     )
               elif label > node.label:
                    __UpperCAmelCase      :					Any    				=     self._put(node.right				,					snake_case				,					snake_case     )
               else:
                    __UpperCAmelCase      :					Any    				=     f'Node with label {label} already exists'
                    raise Exception(snake_case     )

          return node

     def 					lowerCamelCase__					(							self	:						Optional[Any]				,					snake_case	:						int     )		->				Node:
          return self._search(self.root				,					snake_case     )

     def 					lowerCamelCase__					(							self	:						Optional[int]				,					snake_case	:						Node | None				,					snake_case	:						int     )		->				Node:
          if node is None:
               __UpperCAmelCase      :					Optional[int]    				=     f'Node with label {label} does not exist'
               raise Exception(snake_case     )
          else:
               if label < node.label:
                    __UpperCAmelCase      :					str    				=     self._search(node.left				,					snake_case     )
               elif label > node.label:
                    __UpperCAmelCase      :					Any    				=     self._search(node.right				,					snake_case     )

          return node

     def 					lowerCamelCase__					(							self	:						Any				,					snake_case	:						int     )		->				None:
          __UpperCAmelCase      :					List[str]    				=     self.search(snake_case     )
          if node.right and node.left:
               __UpperCAmelCase      :					List[Any]    				=     self._get_lowest_node(node.right     )
               __UpperCAmelCase      :					Optional[int]    				=     node.left
               __UpperCAmelCase      :					List[str]    				=     node.right
               __UpperCAmelCase      :					Any    				=     lowest_node
               if node.right:
                    __UpperCAmelCase      :					Tuple    				=     lowest_node
               self._reassign_nodes(snake_case				,					snake_case     )
          elif not node.right and node.left:
               self._reassign_nodes(snake_case				,					node.left     )
          elif node.right and not node.left:
               self._reassign_nodes(snake_case				,					node.right     )
          else:
               self._reassign_nodes(snake_case				,					snake_case     )

     def 					lowerCamelCase__					(							self	:						Optional[int]				,					snake_case	:						Node				,					snake_case	:						Node | None     )		->				None:
          if new_children:
               __UpperCAmelCase      :					str    				=     node.parent

          if node.parent:
               if node.parent.right == node:
                    __UpperCAmelCase      :					Dict    				=     new_children
               else:
                    __UpperCAmelCase      :					Any    				=     new_children
          else:
               __UpperCAmelCase      :					Optional[Any]    				=     new_children

     def 					lowerCamelCase__					(							self	:						int				,					snake_case	:						Node     )		->				Node:
          if node.left:
               __UpperCAmelCase      :					Optional[Any]    				=     self._get_lowest_node(node.left     )
          else:
               __UpperCAmelCase      :					Tuple    				=     node
               self._reassign_nodes(snake_case				,					node.right     )

          return lowest_node

     def 					lowerCamelCase__					(							self	:						str				,					snake_case	:						int     )		->				bool:
          try:
               self.search(snake_case     )
               return True
          except Exception:
               return False

     def 					lowerCamelCase__					(							self	:						Tuple     )		->				int:
          if self.root is None:
               raise Exception('''Binary search tree is empty'''     )

          __UpperCAmelCase      :					Tuple    				=     self.root
          while node.right is not None:
               __UpperCAmelCase      :					Optional[int]    				=     node.right

          return node.label

     def 					lowerCamelCase__					(							self	:						Optional[Any]     )		->				int:
          if self.root is None:
               raise Exception('''Binary search tree is empty'''     )

          __UpperCAmelCase      :					Dict    				=     self.root
          while node.left is not None:
               __UpperCAmelCase      :					List[str]    				=     node.left

          return node.label

     def 					lowerCamelCase__					(							self	:						int     )		->				Iterator[Node]:
          return self._inorder_traversal(self.root     )

     def 					lowerCamelCase__					(							self	:						Optional[int]				,					snake_case	:						Node | None     )		->				Iterator[Node]:
          if node is not None:
               yield from self._inorder_traversal(node.left     )
               yield node
               yield from self._inorder_traversal(node.right     )

     def 					lowerCamelCase__					(							self	:						Tuple     )		->				Iterator[Node]:
          return self._preorder_traversal(self.root     )






     def 					lowerCamelCase__					(							self	:						List[str]				,					snake_case	:						Node | None     )		->				Iterator[Node]:
          if node is not None:
               yield node
               yield from self._preorder_traversal(node.left     )
               yield from self._preorder_traversal(node.right     )



class       a							(						unittest.TestCase			):


     """simple docstring"""






     @staticmethod
     def 					lowerCamelCase__					(							)		->				BinarySearchTree:
          __UpperCAmelCase      :					List[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 					lowerCamelCase__					(							self	:						Dict     )		->				None:
          __UpperCAmelCase      :					Tuple    				=     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(snake_case     ):  # noqa: B017
               t.put(1     )

     def 					lowerCamelCase__					(							self	:						str     )		->				None:
          __UpperCAmelCase      :					Optional[int]    				=     self._get_binary_search_tree()

          __UpperCAmelCase      :					Optional[int]    				=     t.search(6     )
          assert node.label == 6

          __UpperCAmelCase      :					List[Any]    				=     t.search(13     )
          assert node.label == 13

          with self.assertRaises(snake_case     ):  # noqa: B017
               t.search(2     )

     def 					lowerCamelCase__					(							self	:						str     )		->				None:
          __UpperCAmelCase      :					Optional[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 					lowerCamelCase__					(							self	:						Optional[int]     )		->				None:
          __UpperCAmelCase      :					Tuple    				=     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 					lowerCamelCase__					(							self	:						int     )		->				None:
          __UpperCAmelCase      :					List[str]    				=     self._get_binary_search_tree()
          t.empty()
          assert t.root is None

     def 					lowerCamelCase__					(							self	:						Optional[int]     )		->				None:
          __UpperCAmelCase      :					int    				=     self._get_binary_search_tree()
          assert not t.is_empty()

          t.empty()
          assert t.is_empty()

     def 					lowerCamelCase__					(							self	:						int     )		->				None:
          __UpperCAmelCase      :					Optional[Any]    				=     self._get_binary_search_tree()

          assert t.exists(6     )
          assert not t.exists(-1     )

     def 					lowerCamelCase__					(							self	:						Dict     )		->				None:
          __UpperCAmelCase      :					Union[str, Any]    				=     self._get_binary_search_tree()

          assert t.get_max_label() == 14

          t.empty()
          with self.assertRaises(snake_case     ):  # noqa: B017
               t.get_max_label()

     def 					lowerCamelCase__					(							self	:						Optional[Any]     )		->				None:
          __UpperCAmelCase      :					int    				=     self._get_binary_search_tree()

          assert t.get_min_label() == 1

          t.empty()
          with self.assertRaises(snake_case     ):  # noqa: B017
               t.get_min_label()

     def 					lowerCamelCase__					(							self	:						Tuple     )		->				None:
          __UpperCAmelCase      :					List[Any]    				=     self._get_binary_search_tree()

          __UpperCAmelCase      :					Optional[Any]    				=     [i.label for i in t.inorder_traversal()]
          assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 10, 13, 14]






     def 					lowerCamelCase__					(							self	:						Tuple     )		->				None:
          __UpperCAmelCase      :					Any    				=     self._get_binary_search_tree()

          __UpperCAmelCase      :					str    				=     [i.label for i in t.preorder_traversal()]
          assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 10, 14, 13]




def       _a      (		):





     '''simple docstring'''






     __UpperCAmelCase      :					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    )

     print(
         '''
            8
           / \\
          3   10
         / \\    \\
        1   6    14
           / \\   /
          4   7 13
           \\
            5
        '''    )

     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
     __UpperCAmelCase      :					Optional[int]    				=     [i.label for i in t.inorder_traversal()]
     print('''Inorder traversal:'''     ,   _lowercase    )

     # Prints all the elements of the list in preorder traversal
     __UpperCAmelCase      :					Dict    				=     [i.label for i in t.preorder_traversal()]
     print('''Preorder traversal:'''     ,   _lowercase    )

     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(
         '''
          4
         / \\
        1   7
             \\
              5
        '''    )
     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
     __UpperCAmelCase      :					List[str]    				=     [i.label for i in t.inorder_traversal()]
     print('''Inorder traversal after delete:'''     ,   _lowercase    )

     # Prints all the elements of the list in preorder traversal after delete
     __UpperCAmelCase      :					List[Any]    				=     [i.label for i in t.preorder_traversal()]
     print('''Preorder traversal after delete:'''     ,   _lowercase    )

     print('''Max. label:'''     ,   t.get_max_label()    )
     print('''Min. label:'''     ,   t.get_min_label()    )


if __name__ == "__main__":
      binary_search_tree_example()



'''simple docstring'''



def       _a      (		_lowercase   :      str    ):





     '''simple docstring'''






     __UpperCAmelCase      :					Union[str, Any]    				=     5381
     for x in s:
          __UpperCAmelCase      :					Union[str, Any]    				=     ((hash_value << 5) + hash_value) + ord(_lowercase    )
     return hash_value & 0XFFFFFFFF