



from __future__ import annotations

import unittest
from collections.abc import Iterator

class    _SCREAMING_SNAKE_CASE						:





     def __init__(							self			:				Optional[int]  ,	UpperCamelCase			:				int  ,	UpperCamelCase			:				Node | None					)->None:
      __SCREAMING_SNAKE_CASE							:     str							=						label
      __SCREAMING_SNAKE_CASE							:     Tuple							=						parent
      __SCREAMING_SNAKE_CASE							:     Node | None							=						None
      __SCREAMING_SNAKE_CASE							:     Node | None							=						None






class    _SCREAMING_SNAKE_CASE						:





     def __init__(							self			:				Dict					)->None:
      __SCREAMING_SNAKE_CASE							:     Node | None							=						None





     def 						__snake_case     (							self			:				Optional[Any]					)->None:
      __SCREAMING_SNAKE_CASE							:     int							=						None





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





     def 						__snake_case     (							self			:				List[Any]  ,	UpperCamelCase			:				int					)->None:
      __SCREAMING_SNAKE_CASE							:     Tuple							=						self._put(self.root  ,	UpperCamelCase					)





     def 						__snake_case     (							self			:				List[str]  ,	UpperCamelCase			:				Node | None  ,	UpperCamelCase			:				int  ,	UpperCamelCase			:				Node | None = None					)->Node:
      if node is None:
       __SCREAMING_SNAKE_CASE							:     Optional[int]							=						Node(UpperCamelCase  ,	UpperCamelCase					)
      else:
       if label < node.label:
        __SCREAMING_SNAKE_CASE							:     str							=						self._put(node.left  ,	UpperCamelCase  ,	UpperCamelCase					)
       elif label > node.label:
        __SCREAMING_SNAKE_CASE							:     int							=						self._put(node.right  ,	UpperCamelCase  ,	UpperCamelCase					)
       else:
        __SCREAMING_SNAKE_CASE							:     Any							=						F"""Node with label {label} already exists"""
        raise Exception(UpperCamelCase					)

      return node





     def 						__snake_case     (							self			:				Union[str, Any]  ,	UpperCamelCase			:				int					)->Node:
      return self._search(self.root  ,	UpperCamelCase					)





     def 						__snake_case     (							self			:				List[str]  ,	UpperCamelCase			:				Node | None  ,	UpperCamelCase			:				int					)->Node:
      if node is None:
       __SCREAMING_SNAKE_CASE							:     Dict							=						F"""Node with label {label} does not exist"""
       raise Exception(UpperCamelCase					)
      else:
       if label < node.label:
        __SCREAMING_SNAKE_CASE							:     List[Any]							=						self._search(node.left  ,	UpperCamelCase					)
       elif label > node.label:
        __SCREAMING_SNAKE_CASE							:     Any							=						self._search(node.right  ,	UpperCamelCase					)

      return node





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





     def 						__snake_case     (							self			:				Optional[Any]  ,	UpperCamelCase			:				Node  ,	UpperCamelCase			:				Node | None					)->None:
      if new_children:
       __SCREAMING_SNAKE_CASE							:     Tuple							=						node.parent

      if node.parent:
       if node.parent.right == node:
        __SCREAMING_SNAKE_CASE							:     Optional[int]							=						new_children
       else:
        __SCREAMING_SNAKE_CASE							:     List[Any]							=						new_children
      else:
       __SCREAMING_SNAKE_CASE							:     Optional[Any]							=						new_children





     def 						__snake_case     (							self			:				Union[str, Any]  ,	UpperCamelCase			:				Node					)->Node:
      if node.left:
       __SCREAMING_SNAKE_CASE							:     Union[str, Any]							=						self._get_lowest_node(node.left					)
      else:
       __SCREAMING_SNAKE_CASE							:     List[str]							=						node
       self._reassign_nodes(UpperCamelCase  ,	node.right					)

      return lowest_node





     def 						__snake_case     (							self			:				Optional[Any]  ,	UpperCamelCase			:				int					)->bool:
      try:
       self.search(UpperCamelCase					)
       return True
      except Exception:
       return False





     def 						__snake_case     (							self			:				int					)->int:
      if self.root is None:
       raise Exception("Binary search tree is empty"					)

      __SCREAMING_SNAKE_CASE							:     Optional[Any]							=						self.root
      while node.right is not None:
       __SCREAMING_SNAKE_CASE							:     Union[str, Any]							=						node.right

      return node.label





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

      __SCREAMING_SNAKE_CASE							:     int							=						self.root
      while node.left is not None:
       __SCREAMING_SNAKE_CASE							:     Dict							=						node.left

      return node.label





     def 						__snake_case     (							self			:				Union[str, Any]					)->Iterator[Node]:
      return self._inorder_traversal(self.root					)





     def 						__snake_case     (							self			:				Optional[Any]  ,	UpperCamelCase			:				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 						__snake_case     (							self			:				int					)->Iterator[Node]:
      return self._preorder_traversal(self.root					)






     def 						__snake_case     (							self			:				str  ,	UpperCamelCase			:				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    _SCREAMING_SNAKE_CASE						(unittest.TestCase			):





     @staticmethod
     def 						__snake_case     (							)->BinarySearchTree:
      __SCREAMING_SNAKE_CASE							:     List[str]							=						BinarySearchTree()
      t.put(8					)
      t.put(3					)
      t.put(6					)
      t.put(1					)
      t.put(1_0					)
      t.put(1_4					)
      t.put(1_3					)
      t.put(4					)
      t.put(7					)
      t.put(5					)

      return t





     def 						__snake_case     (							self			:				List[str]					)->None:
      __SCREAMING_SNAKE_CASE							:     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(1_0					)
      assert t.root.right is not None
      assert t.root.right.parent == t.root
      assert t.root.right.label == 1_0

      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(UpperCamelCase					):  # noqa: B017
       t.put(1					)





     def 						__snake_case     (							self			:				int					)->None:
      __SCREAMING_SNAKE_CASE							:     List[Any]							=						self._get_binary_search_tree()

      __SCREAMING_SNAKE_CASE							:     Tuple							=						t.search(6					)
      assert node.label == 6

      __SCREAMING_SNAKE_CASE							:     Tuple							=						t.search(1_3					)
      assert node.label == 1_3

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





     def 						__snake_case     (							self			:				Union[str, Any]					)->None:
      __SCREAMING_SNAKE_CASE							:     Optional[int]							=						self._get_binary_search_tree()

      t.remove(1_3					)
      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 						__snake_case     (							self			:				List[str]					)->None:
      __SCREAMING_SNAKE_CASE							:     int							=						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 						__snake_case     (							self			:				Dict					)->None:
      __SCREAMING_SNAKE_CASE							:     Optional[int]							=						self._get_binary_search_tree()
      t.empty()
      assert t.root is None





     def 						__snake_case     (							self			:				Optional[Any]					)->None:
      __SCREAMING_SNAKE_CASE							:     Optional[int]							=						self._get_binary_search_tree()
      assert not t.is_empty()

      t.empty()
      assert t.is_empty()





     def 						__snake_case     (							self			:				Dict					)->None:
      __SCREAMING_SNAKE_CASE							:     Any							=						self._get_binary_search_tree()

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





     def 						__snake_case     (							self			:				Optional[int]					)->None:
      __SCREAMING_SNAKE_CASE							:     List[str]							=						self._get_binary_search_tree()

      assert t.get_max_label() == 1_4

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





     def 						__snake_case     (							self			:				List[str]					)->None:
      __SCREAMING_SNAKE_CASE							:     int							=						self._get_binary_search_tree()

      assert t.get_min_label() == 1

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





     def 						__snake_case     (							self			:				str					)->None:
      __SCREAMING_SNAKE_CASE							:     List[Any]							=						self._get_binary_search_tree()

      __SCREAMING_SNAKE_CASE							:     str							=						[i.label for i in t.inorder_traversal()]
      assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 1_0, 1_3, 1_4]






     def 						__snake_case     (							self			:				int					)->None:
      __SCREAMING_SNAKE_CASE							:     List[Any]							=						self._get_binary_search_tree()

      __SCREAMING_SNAKE_CASE							:     int							=						[i.label for i in t.preorder_traversal()]
      assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 1_0, 1_4, 1_3]






def 						_lowerCAmelCase    (					):



 """simple docstring"""





 __SCREAMING_SNAKE_CASE							:     Optional[int]							=						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
 __SCREAMING_SNAKE_CASE							:     Optional[Any]							=						[i.label for i in t.inorder_traversal()]
 print("Inorder traversal:"		,						__lowerCamelCase  )

 # Prints all the elements of the list in preorder traversal
 __SCREAMING_SNAKE_CASE							:     List[Any]							=						[i.label for i in t.preorder_traversal()]
 print("Preorder traversal:"		,						__lowerCamelCase  )

 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
 __SCREAMING_SNAKE_CASE							:     Union[str, Any]							=						[i.label for i in t.inorder_traversal()]
 print("Inorder traversal after delete:"		,						__lowerCamelCase  )

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

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


if __name__ == "__main__":
      binary_search_tree_example()








from __future__ import annotations

from typing import Any

class        UpperCamelCase__:

	"""simple docstring"""

	def __init__(      self				:			Dict							,			snake_case__				:			Any							,			snake_case__				:			Any ):  # noqa: A002
			"""simple docstring"""





			A				=item
			A				=next


class        UpperCamelCase__:

	"""simple docstring"""

	def __init__(      self				:			Optional[Any] ):
			"""simple docstring"""





			A				=None
			A				=0







	def        _a					(      self				:			str							,			snake_case__				:			Any ):
			"""simple docstring"""





			A				=Node(snake_case__							,			self.head )
			self.size += 1







	def        _a					(      self				:			Dict ):
			"""simple docstring"""





			if self.head is None:
					return None
			else:
					A				=self.head.item
					A				=self.head.next
					self.size -= 1
					return item







	def        _a					(      self				:			Any ):
			"""simple docstring"""





			return self.head is None







	def __str__(      self				:			Dict ):
			"""simple docstring"""





			if self.is_empty():
					return ""
			else:
					A				=self.head
					A				=""
					A				=[]
					while iterate:
							item_list.append(str(iterate.item ) )
							A				=iterate.next

					A				=" --> ".join(snake_case__ )

					return item_str







	def __len__(      self				:			Union[str, Any] ):
			"""simple docstring"""





			return self.size




