




'''simple docstring'''







from __future__ import annotations

import unittest
from collections.abc import Iterator

class   _snake_case:






 def __init__(self					:     Optional[int]						,		a					:     int						,		a					:     Node | None						)					->      None:






    """simple docstring"""


    A__         =    label
    A__         =    parent
    A__         =    None
    A__         =    None




class   _snake_case:






 def __init__(self					:     Tuple						)					->      None:






    """simple docstring"""


    A__         =    None






 def 	_UpperCamelCase   (self					:     List[Any]						)					->      None:






    """simple docstring"""


    A__         =    None






 def 	_UpperCamelCase   (self					:     Tuple						)					->      bool:






    """simple docstring"""


    return self.root is None






 def 	_UpperCamelCase   (self					:     str						,		a					:     int						)					->      None:






    """simple docstring"""


    A__         =    self._put(self.root						,		a						)






 def 	_UpperCamelCase   (self					:     Optional[int]						,		a					:     Node | None						,		a					:     int						,		a					:     Node | None = None						)					->      Node:






    """simple docstring"""


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

    return node






 def 	_UpperCamelCase   (self					:     Optional[Any]						,		a					:     int						)					->      Node:






    """simple docstring"""


    return self._search(self.root						,		a						)






 def 	_UpperCamelCase   (self					:     str						,		a					:     Node | None						,		a					:     int						)					->      Node:






    """simple docstring"""


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

    return node






 def 	_UpperCamelCase   (self					:     List[Any]						,		a					:     int						)					->      None:






    """simple docstring"""


    A__         =    self.search(a						)
    if node.right and node.left:
       A__         =    self._get_lowest_node(node.right						)
       A__         =    node.left
       A__         =    node.right
       A__         =    lowest_node
       if node.right:
          A__         =    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					:     str						,		a					:     Node						,		a					:     Node | None						)					->      None:






    """simple docstring"""


    if new_children:
       A__         =    node.parent

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






 def 	_UpperCamelCase   (self					:     Dict						,		a					:     Node						)					->      Node:






    """simple docstring"""


    if node.left:
       A__         =    self._get_lowest_node(node.left						)
    else:
       A__         =    node
       self._reassign_nodes(a						,		node.right						)

    return lowest_node






 def 	_UpperCamelCase   (self					:     int						,		a					:     int						)					->      bool:






    """simple docstring"""


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






 def 	_UpperCamelCase   (self					:     Tuple						)					->      int:






    """simple docstring"""


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

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

    return node.label






 def 	_UpperCamelCase   (self					:     List[str]						)					->      int:






    """simple docstring"""


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

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

    return node.label






 def 	_UpperCamelCase   (self					:     Dict						)					->      Iterator[Node]:






    """simple docstring"""


    return self._inorder_traversal(self.root						)






 def 	_UpperCamelCase   (self					:     List[Any]						,		a					:     Node | None						)					->      Iterator[Node]:






    """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					:     Any						)					->      Iterator[Node]:






    """simple docstring"""


    return self._preorder_traversal(self.root						)






 def 	_UpperCamelCase   (self					:     Optional[int]						,		a					:     Node | None						)					->      Iterator[Node]:






    """simple docstring"""


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




class   _snake_case( unittest.TestCase			):






 @staticmethod
 def 	_UpperCamelCase   ()					->      BinarySearchTree:






    """simple docstring"""


    A__         =    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					:     Union[str, Any]						)					->      None:






    """simple docstring"""


    A__         =    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					:     Tuple						)					->      None:






    """simple docstring"""


    A__         =    self._get_binary_search_tree()

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

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

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






 def 	_UpperCamelCase   (self					:     Any						)					->      None:






    """simple docstring"""


    A__         =    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					:     str						)					->      None:






    """simple docstring"""


    A__         =    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					:     Union[str, Any]						)					->      None:






    """simple docstring"""


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






 def 	_UpperCamelCase   (self					:     List[Any]						)					->      None:






    """simple docstring"""


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

    t.empty()
    assert t.is_empty()






 def 	_UpperCamelCase   (self					:     Any						)					->      None:






    """simple docstring"""


    A__         =    self._get_binary_search_tree()

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






 def 	_UpperCamelCase   (self					:     Tuple						)					->      None:






    """simple docstring"""


    A__         =    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					:     List[str]						)					->      None:






    """simple docstring"""


    A__         =    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					:     int						)					->      None:






    """simple docstring"""


    A__         =    self._get_binary_search_tree()

    A__         =    [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					:     str						)					->      None:






    """simple docstring"""


    A__         =    self._get_binary_search_tree()

    A__         =    [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'''







   A__         =    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__         =    [i.label for i in t.inorder_traversal()]
   print('Inorder traversal:'			,UpperCAmelCase	)

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








'''simple docstring'''







def 	_A			(   UpperCAmelCase	):






   '''simple docstring'''







   if not isinstance(UpperCAmelCase			,UpperCAmelCase	) or not all(
       isinstance(UpperCAmelCase			,UpperCAmelCase	) and item >= 0 for item in citations	):
      raise ValueError('The citations should be a list of non negative integers.'	)

   citations.sort()
   A__         =    len(UpperCAmelCase	)

   for i in range(UpperCAmelCase	):
      if citations[len_citations - 1 - i] <= i:
         return i

   return len_citations


if __name__ == "__main__":
    import doctest

    doctest.testmod()


