






"""simple docstring"""





from __future__ import annotations

import unittest
from collections.abc import Iterator







class 		_a       :





   '''simple docstring'''






   def __init__(   self			,				UpperCAmelCase_			,				UpperCAmelCase_)	-> None:




          '''simple docstring'''




          lowercase__:    Dict        =      label
          lowercase__:    List[Any]        =      parent
          lowercase__:    Node | None        =      None
          lowercase__:    Node | None        =      None







class 		_a       :





   '''simple docstring'''






   def __init__(   self)	-> None:




          '''simple docstring'''




          lowercase__:    Node | None        =      None





   def __lowercase    (   self)	-> None:




          '''simple docstring'''




          lowercase__:    List[str]        =      None





   def __lowercase    (   self)	-> bool:




          '''simple docstring'''




          return self.root is None





   def __lowercase    (   self			,				UpperCAmelCase_)	-> None:




          '''simple docstring'''




          lowercase__:    List[str]        =      self._put(self.root			,				UpperCAmelCase_)





   def __lowercase    (   self			,				UpperCAmelCase_			,				UpperCAmelCase_			,				UpperCAmelCase_ = None)	-> Node:




          '''simple docstring'''




          if node is None:
                 lowercase__:    List[Any]        =      Node(UpperCAmelCase_			,				UpperCAmelCase_)
          else:
                 if label < node.label:
                        lowercase__:    str        =      self._put(node.left			,				UpperCAmelCase_			,				UpperCAmelCase_)
                 elif label > node.label:
                        lowercase__:    int        =      self._put(node.right			,				UpperCAmelCase_			,				UpperCAmelCase_)
                 else:
                        lowercase__:    List[Any]        =      F"""Node with label {label} already exists"""
                        raise Exception(UpperCAmelCase_)

          return node





   def __lowercase    (   self			,				UpperCAmelCase_)	-> Node:




          '''simple docstring'''




          return self._search(self.root			,				UpperCAmelCase_)





   def __lowercase    (   self			,				UpperCAmelCase_			,				UpperCAmelCase_)	-> Node:




          '''simple docstring'''




          if node is None:
                 lowercase__:    int        =      F"""Node with label {label} does not exist"""
                 raise Exception(UpperCAmelCase_)
          else:
                 if label < node.label:
                        lowercase__:    str        =      self._search(node.left			,				UpperCAmelCase_)
                 elif label > node.label:
                        lowercase__:    List[str]        =      self._search(node.right			,				UpperCAmelCase_)

          return node





   def __lowercase    (   self			,				UpperCAmelCase_)	-> None:




          '''simple docstring'''




          lowercase__:    Optional[Any]        =      self.search(UpperCAmelCase_)
          if node.right and node.left:
                 lowercase__:    List[str]        =      self._get_lowest_node(node.right)
                 lowercase__:    Any        =      node.left
                 lowercase__:    Any        =      node.right
                 lowercase__:    Dict        =      lowest_node
                 if node.right:
                        lowercase__:    List[str]        =      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 __lowercase    (   self			,				UpperCAmelCase_			,				UpperCAmelCase_)	-> None:




          '''simple docstring'''




          if new_children:
                 lowercase__:    Union[str, Any]        =      node.parent

          if node.parent:
                 if node.parent.right == node:
                        lowercase__:    str        =      new_children
                 else:
                        lowercase__:    Union[str, Any]        =      new_children
          else:
                 lowercase__:    Tuple        =      new_children





   def __lowercase    (   self			,				UpperCAmelCase_)	-> Node:




          '''simple docstring'''




          if node.left:
                 lowercase__:    int        =      self._get_lowest_node(node.left)
          else:
                 lowercase__:    List[str]        =      node
                 self._reassign_nodes(UpperCAmelCase_			,				node.right)

          return lowest_node





   def __lowercase    (   self			,				UpperCAmelCase_)	-> bool:




          '''simple docstring'''




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





   def __lowercase    (   self)	-> int:




          '''simple docstring'''




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

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

          return node.label





   def __lowercase    (   self)	-> int:




          '''simple docstring'''




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

          lowercase__:    Tuple        =      self.root
          while node.left is not None:
                 lowercase__:    int        =      node.left

          return node.label





   def __lowercase    (   self)	-> Iterator[Node]:




          '''simple docstring'''




          return self._inorder_traversal(self.root)





   def __lowercase    (   self			,				UpperCAmelCase_)	-> 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 __lowercase    (   self)	-> Iterator[Node]:




          '''simple docstring'''




          return self._preorder_traversal(self.root)





   def __lowercase    (   self			,				UpperCAmelCase_)	-> 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 		_a       (						unittest.TestCase   ):





   '''simple docstring'''






   @staticmethod
   def __lowercase    (   )	-> BinarySearchTree:




          '''simple docstring'''




          lowercase__:    Optional[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)

          return t





   def __lowercase    (   self)	-> None:




          '''simple docstring'''




          lowercase__:    int        =      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(UpperCAmelCase_):  # noqa: B017
                 t.put(1)





   def __lowercase    (   self)	-> None:




          '''simple docstring'''




          lowercase__:    Optional[int]        =      self._get_binary_search_tree()

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

          lowercase__:    List[str]        =      t.search(13)
          assert node.label == 13

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





   def __lowercase    (   self)	-> None:




          '''simple docstring'''




          lowercase__:    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 __lowercase    (   self)	-> None:




          '''simple docstring'''




          lowercase__:    Dict        =      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)	-> None:




          '''simple docstring'''




          lowercase__:    Union[str, Any]        =      self._get_binary_search_tree()
          t.empty()
          assert t.root is None





   def __lowercase    (   self)	-> None:




          '''simple docstring'''




          lowercase__:    Union[str, Any]        =      self._get_binary_search_tree()
          assert not t.is_empty()

          t.empty()
          assert t.is_empty()





   def __lowercase    (   self)	-> None:




          '''simple docstring'''




          lowercase__:    Optional[int]        =      self._get_binary_search_tree()

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





   def __lowercase    (   self)	-> None:




          '''simple docstring'''




          lowercase__:    Optional[int]        =      self._get_binary_search_tree()

          assert t.get_max_label() == 14

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





   def __lowercase    (   self)	-> None:




          '''simple docstring'''




          lowercase__:    List[str]        =      self._get_binary_search_tree()

          assert t.get_min_label() == 1

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





   def __lowercase    (   self)	-> None:




          '''simple docstring'''




          lowercase__:    List[Any]        =      self._get_binary_search_tree()

          lowercase__:    List[Any]        =      [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)	-> None:




          '''simple docstring'''




          lowercase__:    List[Any]        =      self._get_binary_search_tree()

          lowercase__:    Dict        =      [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"""





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

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

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

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

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


if __name__ == "__main__":
  binary_search_tree_example()














"""simple docstring"""





class 		_a       :





   '''simple docstring'''






   def __init__(   self			,				UpperCAmelCase_=None)	-> List[Any]:




          '''simple docstring'''




          lowercase__:    str        =      data
          lowercase__:    Any        =      None





   def __repr__(   self)	-> Optional[Any]:




          '''simple docstring'''




          lowercase__:    Any        =      ""
          lowercase__:    Dict        =      self
          while temp:
                 string_rep += F"""<{temp.data}> ---> """
                 lowercase__:    Tuple        =      temp.next
          string_rep += "<END>"
          return string_rep







def     A(  snake_case_		):
       """simple docstring"""





       if not elements_list:
              raise Exception("The Elements List is empty"		)

       # Set first element as Head
       lowercase__:    Any        =      Node(elements_list[0]		)
       lowercase__:    Optional[int]        =      head
       # Loop through elements from position 1
       for data in elements_list[1:]:
              lowercase__:    Dict        =      Node(snake_case_		)
              lowercase__:    Dict        =      current.next
       return head


UpperCamelCase			=      [1, 3, 5, 32, 44, 12, 43]
print(F"List: {list_data}")
print("""Creating Linked List from List.""")
UpperCamelCase			=      make_linked_list(list_data)
print("""Linked List:""")







print(linked_list)






