from __future__ import annotations

import unittest
from collections.abc import Iterator






class     __UpperCAmelCase:






 """simple docstring"""




 def __init__(    self ,       __magic_name__ ,       __magic_name__      ):

        """simple docstring"""

        A_							:       Optional[Any]	      =				label
        A_							:       str	      =				parent
        A_							:       List[Any]	      =				None
        A_							:       List[Any]	      =				None






class     __UpperCAmelCase:






 """simple docstring"""




 def __init__(    self      ):

        """simple docstring"""

        A_							:       Optional[int]	      =				None
 def  UpperCAmelCase   (    self      ):

        """simple docstring"""

        A_							:       Tuple	      =				None
 def  UpperCAmelCase   (    self      ):

        """simple docstring"""

        return self.root is None
 def  UpperCAmelCase   (    self ,       __magic_name__      ):

        """simple docstring"""

        A_							:       Optional[int]	      =				self._put(self.root ,       _lowerCAmelCase      )
 def  UpperCAmelCase   (    self ,       __magic_name__ ,       __magic_name__ ,       __magic_name__ = None      ):

        """simple docstring"""

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

        return node
 def  UpperCAmelCase   (    self ,       __magic_name__      ):

        """simple docstring"""

        return self._search(self.root ,       _lowerCAmelCase      )
 def  UpperCAmelCase   (    self ,       __magic_name__ ,       __magic_name__      ):

        """simple docstring"""

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

        return node
 def  UpperCAmelCase   (    self ,       __magic_name__      ):

        """simple docstring"""

        A_							:       Any	      =				self.search(_lowerCAmelCase      )
        if node.right and node.left:
               A_							:       Optional[int]	      =				self._get_lowest_node(node.right      )
               A_							:       List[str]	      =				node.left
               A_							:       int	      =				node.right
               A_							:       Union[str, Any]	      =				lowest_node
               if node.right:
                      A_							:       int	      =				lowest_node
               self._reassign_nodes(_lowerCAmelCase ,       _lowerCAmelCase      )
        elif not node.right and node.left:
               self._reassign_nodes(_lowerCAmelCase ,       node.left      )
        elif node.right and not node.left:
               self._reassign_nodes(_lowerCAmelCase ,       node.right      )
        else:
               self._reassign_nodes(_lowerCAmelCase ,       _lowerCAmelCase      )
 def  UpperCAmelCase   (    self ,       __magic_name__ ,       __magic_name__      ):

        """simple docstring"""

        if new_children:
               A_							:       Optional[Any]	      =				node.parent

        if node.parent:
               if node.parent.right == node:
                      A_							:       str	      =				new_children
               else:
                      A_							:       Tuple	      =				new_children
        else:
               A_							:       Tuple	      =				new_children
 def  UpperCAmelCase   (    self ,       __magic_name__      ):

        """simple docstring"""

        if node.left:
               A_							:       Optional[int]	      =				self._get_lowest_node(node.left      )
        else:
               A_							:       int	      =				node
               self._reassign_nodes(_lowerCAmelCase ,       node.right      )

        return lowest_node
 def  UpperCAmelCase   (    self ,       __magic_name__      ):

        """simple docstring"""

        try:
               self.search(_lowerCAmelCase      )
               return True
        except Exception:
               return False
 def  UpperCAmelCase   (    self      ):

        """simple docstring"""

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

        A_							:       str	      =				self.root
        while node.right is not None:
               A_							:       Tuple	      =				node.right

        return node.label
 def  UpperCAmelCase   (    self      ):

        """simple docstring"""

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

        A_							:       List[Any]	      =				self.root
        while node.left is not None:
               A_							:       Dict	      =				node.left

        return node.label
 def  UpperCAmelCase   (    self      ):

        """simple docstring"""

        return self._inorder_traversal(self.root      )
 def  UpperCAmelCase   (    self ,       __magic_name__      ):

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

        """simple docstring"""

        return self._preorder_traversal(self.root      )
 def  UpperCAmelCase   (    self ,       __magic_name__      ):

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






 """simple docstring"""




 @staticmethod
 def  UpperCAmelCase   (    ):

        """simple docstring"""

        A_							:       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  UpperCAmelCase   (    self      ):

        """simple docstring"""

        A_							:       Dict	      =				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(_lowerCAmelCase      ):  # noqa: B017
               t.put(1      )
 def  UpperCAmelCase   (    self      ):

        """simple docstring"""

        A_							:       Union[str, Any]	      =				self._get_binary_search_tree()

        A_							:       List[Any]	      =				t.search(6      )
        assert node.label == 6

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

        with self.assertRaises(_lowerCAmelCase      ):  # noqa: B017
               t.search(2      )
 def  UpperCAmelCase   (    self      ):

        """simple docstring"""

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

        """simple docstring"""

        A_							:       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  UpperCAmelCase   (    self      ):

        """simple docstring"""

        A_							:       List[Any]	      =				self._get_binary_search_tree()
        t.empty()
        assert t.root is None
 def  UpperCAmelCase   (    self      ):

        """simple docstring"""

        A_							:       Dict	      =				self._get_binary_search_tree()
        assert not t.is_empty()

        t.empty()
        assert t.is_empty()
 def  UpperCAmelCase   (    self      ):

        """simple docstring"""

        A_							:       Dict	      =				self._get_binary_search_tree()

        assert t.exists(6      )
        assert not t.exists(-1      )
 def  UpperCAmelCase   (    self      ):

        """simple docstring"""

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

        assert t.get_max_label() == 14

        t.empty()
        with self.assertRaises(_lowerCAmelCase      ):  # noqa: B017
               t.get_max_label()
 def  UpperCAmelCase   (    self      ):

        """simple docstring"""

        A_							:       Any	      =				self._get_binary_search_tree()

        assert t.get_min_label() == 1

        t.empty()
        with self.assertRaises(_lowerCAmelCase      ):  # noqa: B017
               t.get_min_label()
 def  UpperCAmelCase   (    self      ):

        """simple docstring"""

        A_							:       int	      =				self._get_binary_search_tree()

        A_							:       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  UpperCAmelCase   (    self      ):

        """simple docstring"""

        A_							:       str	      =				self._get_binary_search_tree()

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


def       a__      (					)		->	None:
       A_							:       List[Any]	      =				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							)

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

       print('''Label 6 exists:'''  ,   t.exists(6							)							)
       print('''Label 13 exists:'''  ,   t.exists(1_3							)							)
       print('''Label -1 exists:'''  ,   t.exists(-1							)							)
       print('''Label 12 exists:'''  ,   t.exists(1_2							)							)

       # Prints all the elements of the list in inorder traversal
       A_							:       Optional[Any]	      =				[i.label for i in t.inorder_traversal()]
       print('''Inorder traversal:'''  ,   _SCREAMING_SNAKE_CASE							)

       # Prints all the elements of the list in preorder traversal
       A_							:       List[Any]	      =				[i.label for i in t.preorder_traversal()]
       print('''Preorder traversal:'''  ,   _SCREAMING_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(
           '''
          4
         / \\
        1   7
             \\
              5
        '''							)
       t.remove(1_3							)
       t.remove(1_0							)
       t.remove(8							)
       t.remove(3							)
       t.remove(6							)
       t.remove(1_4							)

       # Prints all the elements of the list in inorder traversal after delete
       A_							:       Optional[Any]	      =				[i.label for i in t.inorder_traversal()]
       print('''Inorder traversal after delete:'''  ,   _SCREAMING_SNAKE_CASE							)

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

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


if __name__ == "__main__":
    binary_search_tree_example()







import math
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						int					)->bool:

      if 1 < number < 4:
            # 2 and 3 are primes
            return True
      elif number < 2 or number % 2 == 0 or number % 3 == 0:
            # Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
            return False

      # All primes number are in format of 6k +/- 1
      for i in range(5  ,					int(math.sqrt(_SCREAMING_SNAKE_CASE					) + 1					)  ,					6					):
            if number % i == 0 or number % (i + 2) == 0:
                  return False
      return True
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						int = 6_0_0_8_5_1_4_7_5_1_4_3					)->int:

      try:
            _lowerCAmelCase			      =	int(_SCREAMING_SNAKE_CASE					)
      except (TypeError, ValueError):
            raise TypeError('''Parameter n must be int or castable to int.'''					)
      if n <= 0:
            raise ValueError('''Parameter n must be greater than or equal to one.'''					)
      _lowerCAmelCase			      =	0
      if is_prime(_SCREAMING_SNAKE_CASE					):
            return n
      while n % 2 == 0:
            n //= 2
      if is_prime(_SCREAMING_SNAKE_CASE					):
            return n
      for i in range(3  ,					int(math.sqrt(_SCREAMING_SNAKE_CASE					)					) + 1  ,					2					):
            if n % i == 0:
                  if is_prime(n // i					):
                        _lowerCAmelCase			      =	n // i
                        break
                  elif is_prime(_SCREAMING_SNAKE_CASE					):
                        _lowerCAmelCase			      =	i
      return max_number


if __name__ == "__main__":
    print(F"""{solution() = }""")