


'''simple docstring'''

from __future__ import annotations

import unittest
from collections.abc import Iterator







class        UpperCAmelCase       :

 def __init__(       self       :		List[Any],    a_       :		Tuple,    a_       :		Tuple    ):





    """simple docstring"""



    UpperCamelCase__         =  label
    UpperCamelCase__         =  parent
    UpperCamelCase__         =  None
    UpperCamelCase__         =  None







class        UpperCAmelCase       :

 def __init__(       self       :		Union[str, Any]    ):





    """simple docstring"""



    UpperCamelCase__         =  None

 def 						lowercase_  (       self       :		Dict    ):





    """simple docstring"""



    UpperCamelCase__         =  None

 def 						lowercase_  (       self       :		Union[str, Any]    ):





    """simple docstring"""



    return self.root is None

 def 						lowercase_  (       self       :		List[str],    a_       :		Optional[Any]    ):





    """simple docstring"""



    UpperCamelCase__         =  self._put(self.root,    a_    )

 def 						lowercase_  (       self       :		Tuple,    a_       :		List[Any],    a_       :		int,    a_       :		Dict = None    ):





    """simple docstring"""



    if node is None:
       UpperCamelCase__         =  Node(a_,    a_    )
    else:
       if label < node.label:
          UpperCamelCase__         =  self._put(node.left,    a_,    a_    )
       elif label > node.label:
          UpperCamelCase__         =  self._put(node.right,    a_,    a_    )
       else:
          UpperCamelCase__         =  f'Node with label {label} already exists'
          raise Exception(a_    )

    return node

 def 						lowercase_  (       self       :		Tuple,    a_       :		Dict    ):





    """simple docstring"""



    return self._search(self.root,    a_    )

 def 						lowercase_  (       self       :		Union[str, Any],    a_       :		Tuple,    a_       :		Tuple    ):





    """simple docstring"""



    if node is None:
       UpperCamelCase__         =  f'Node with label {label} does not exist'
       raise Exception(a_    )
    else:
       if label < node.label:
          UpperCamelCase__         =  self._search(node.left,    a_    )
       elif label > node.label:
          UpperCamelCase__         =  self._search(node.right,    a_    )

    return node

 def 						lowercase_  (       self       :		List[Any],    a_       :		Tuple    ):





    """simple docstring"""



    UpperCamelCase__         =  self.search(a_    )
    if node.right and node.left:
       UpperCamelCase__         =  self._get_lowest_node(node.right    )
       UpperCamelCase__         =  node.left
       UpperCamelCase__         =  node.right
       UpperCamelCase__         =  lowest_node
       if node.right:
          UpperCamelCase__         =  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 						lowercase_  (       self       :		Dict,    a_       :		int,    a_       :		int    ):





    """simple docstring"""



    if new_children:
       UpperCamelCase__         =  node.parent

    if node.parent:
       if node.parent.right == node:
          UpperCamelCase__         =  new_children
       else:
          UpperCamelCase__         =  new_children
    else:
       UpperCamelCase__         =  new_children

 def 						lowercase_  (       self       :		Dict,    a_       :		Optional[Any]    ):





    """simple docstring"""



    if node.left:
       UpperCamelCase__         =  self._get_lowest_node(node.left    )
    else:
       UpperCamelCase__         =  node
       self._reassign_nodes(a_,    node.right    )

    return lowest_node

 def 						lowercase_  (       self       :		Optional[Any],    a_       :		Dict    ):





    """simple docstring"""



    try:
       self.search(a_    )
       return True
    except Exception:
       return False

 def 						lowercase_  (       self       :		Optional[int]    ):





    """simple docstring"""



    if self.root is None:
       raise Exception("Binary search tree is empty"    )

    UpperCamelCase__         =  self.root
    while node.right is not None:
       UpperCamelCase__         =  node.right

    return node.label

 def 						lowercase_  (       self       :		Tuple    ):





    """simple docstring"""



    if self.root is None:
       raise Exception("Binary search tree is empty"    )

    UpperCamelCase__         =  self.root
    while node.left is not None:
       UpperCamelCase__         =  node.left

    return node.label

 def 						lowercase_  (       self       :		Optional[int]    ):





    """simple docstring"""



    return self._inorder_traversal(self.root    )

 def 						lowercase_  (       self       :		Optional[Any],    a_       :		Dict    ):





    """simple docstring"""



    if node is not None:
       yield from self._inorder_traversal(node.left    )
       yield node
       yield from self._inorder_traversal(node.right    )

 def 						lowercase_  (       self       :		Dict    ):





    """simple docstring"""



    return self._preorder_traversal(self.root    )

 def 						lowercase_  (       self       :		Optional[int],    a_       :		Tuple    ):





    """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 						lowercase_  (       ):





    """simple docstring"""



    UpperCamelCase__         =  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 						lowercase_  (       self       :		Dict    ):





    """simple docstring"""



    UpperCamelCase__         =  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 						lowercase_  (       self       :		Tuple    ):





    """simple docstring"""



    UpperCamelCase__         =  self._get_binary_search_tree()

    UpperCamelCase__         =  t.search(6    )
    assert node.label == 6

    UpperCamelCase__         =  t.search(13    )
    assert node.label == 13

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

 def 						lowercase_  (       self       :		List[Any]    ):





    """simple docstring"""



    UpperCamelCase__         =  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 						lowercase_  (       self       :		Optional[Any]    ):





    """simple docstring"""



    UpperCamelCase__         =  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 						lowercase_  (       self       :		Dict    ):





    """simple docstring"""



    UpperCamelCase__         =  self._get_binary_search_tree()
    t.empty()
    assert t.root is None

 def 						lowercase_  (       self       :		int    ):





    """simple docstring"""



    UpperCamelCase__         =  self._get_binary_search_tree()
    assert not t.is_empty()

    t.empty()
    assert t.is_empty()

 def 						lowercase_  (       self       :		Any    ):





    """simple docstring"""



    UpperCamelCase__         =  self._get_binary_search_tree()

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

 def 						lowercase_  (       self       :		List[str]    ):





    """simple docstring"""



    UpperCamelCase__         =  self._get_binary_search_tree()

    assert t.get_max_label() == 14

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

 def 						lowercase_  (       self       :		Tuple    ):





    """simple docstring"""



    UpperCamelCase__         =  self._get_binary_search_tree()

    assert t.get_min_label() == 1

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

 def 						lowercase_  (       self       :		Optional[int]    ):





    """simple docstring"""



    UpperCamelCase__         =  self._get_binary_search_tree()

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

 def 						lowercase_  (       self       :		Tuple    ):





    """simple docstring"""



    UpperCamelCase__         =  self._get_binary_search_tree()

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







def 				SCREAMING_SNAKE_CASE__(						)						->    None:





   '''simple docstring'''







   UpperCamelCase__         =  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
   UpperCamelCase__         =  [i.label for i in t.inorder_traversal()]
   print("Inorder traversal:"			,						_UpperCamelCase      )

   # Prints all the elements of the list in preorder traversal
   UpperCamelCase__         =  [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
   UpperCamelCase__         =  [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
   UpperCamelCase__         =  [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()





from typing import Any





class 		A__				:






	def __init__(	self						)      ->   int:




						"""simple docstring"""






						__magic_name__					:							List[str]		   =							[]
						__magic_name__					:							str		   =							0






	def __str__(	self						)      ->   Union[str, Any]:




						"""simple docstring"""






						__magic_name__					:							str		   =							'''<''' + str(self.stack						)[1:-1] + '''>'''
						return printed






	def  lowercase      (	self				,     lowerCamelCase						)      ->   None:




						"""simple docstring"""






						self.stack.append(lowerCamelCase						)
						__magic_name__					:							Tuple		   =							self.length + 1






	def  lowercase      (	self						)      ->   Any:




						"""simple docstring"""






						self.rotate(1						)
						__magic_name__					:							Union[str, Any]		   =							self.stack[self.length - 1]
						__magic_name__					:							Union[str, Any]		   =							self.stack[:-1]
						self.rotate(self.length - 1						)
						__magic_name__					:							List[Any]		   =							self.length - 1
						return dequeued






	def  lowercase      (	self				,     lowerCamelCase						)      ->   None:




						"""simple docstring"""






						for _ in range(lowerCamelCase						):
											__magic_name__					:							str		   =							self.stack[0]
											__magic_name__					:							Optional[Any]		   =							self.stack[1:]
											self.put(lowerCamelCase						)
											__magic_name__					:							List[Any]		   =							self.length - 1






	def  lowercase      (	self						)      ->   Any:




						"""simple docstring"""






						__magic_name__					:							Optional[int]		   =							self.get()
						self.put(lowerCamelCase						)
						self.rotate(self.length - 1						)
						return front






	def  lowercase      (	self						)      ->   int:




						"""simple docstring"""






						return self.length



