





'''simple docstring'''





from __future__ import annotations

import unittest
from collections.abc import Iterator





class A_      :




   def __init__(self			:Optional[Any]					,     _UpperCamelCase			:int					,     _UpperCamelCase			:Node | None				)->      None:
         __A      =       label
         __A      =       parent
         __A      =       None
         __A      =       None





class A_      :




   def __init__(self			:str				)->      None:
         __A      =       None




   def _lowerCAmelCase   (self			:str				)->      None:
         __A      =       None




   def _lowerCAmelCase   (self			:int				)->      bool:
         return self.root is None




   def _lowerCAmelCase   (self			:int					,     _UpperCamelCase			:int				)->      None:
         __A      =       self._put(self.root					,     _UpperCamelCase				)




   def _lowerCAmelCase   (self			:int					,     _UpperCamelCase			:Node | None					,     _UpperCamelCase			:int					,     _UpperCamelCase			:Node | None = None				)->      Node:
         if node is None:
               __A      =       Node(_UpperCamelCase					,     _UpperCamelCase				)
         else:
               if label < node.label:
                     __A      =       self._put(node.left					,     _UpperCamelCase					,     _UpperCamelCase				)
               elif label > node.label:
                     __A      =       self._put(node.right					,     _UpperCamelCase					,     _UpperCamelCase				)
               else:
                     __A      =       f"""Node with label {label} already exists"""
                     raise Exception(_UpperCamelCase				)

         return node




   def _lowerCAmelCase   (self			:Tuple					,     _UpperCamelCase			:int				)->      Node:
         return self._search(self.root					,     _UpperCamelCase				)




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

         return node




   def _lowerCAmelCase   (self			:Any					,     _UpperCamelCase			:int				)->      None:
         __A      =       self.search(_UpperCamelCase				)
         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(_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 _lowerCAmelCase   (self			:int					,     _UpperCamelCase			:Node					,     _UpperCamelCase			:Node | None				)->      None:
         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 _lowerCAmelCase   (self			:Optional[int]					,     _UpperCamelCase			:Node				)->      Node:
         if node.left:
               __A      =       self._get_lowest_node(node.left				)
         else:
               __A      =       node
               self._reassign_nodes(_UpperCamelCase					,     node.right				)

         return lowest_node




   def _lowerCAmelCase   (self			:str					,     _UpperCamelCase			:int				)->      bool:
         try:
               self.search(_UpperCamelCase				)
               return True
         except Exception:
               return False




   def _lowerCAmelCase   (self			:Optional[int]				)->      int:
         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 _lowerCAmelCase   (self			:List[str]				)->      int:
         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 _lowerCAmelCase   (self			:List[Any]				)->      Iterator[Node]:
         return self._inorder_traversal(self.root				)




   def _lowerCAmelCase   (self			:str					,     _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 _lowerCAmelCase   (self			:Any				)->      Iterator[Node]:
         return self._preorder_traversal(self.root				)






   def _lowerCAmelCase   (self			:Optional[Any]					,     _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 A_      (    unittest.TestCase     ):




   @staticmethod
   def _lowerCAmelCase   ()->      BinarySearchTree:
         __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 _lowerCAmelCase   (self			:int				)->      None:
         __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(_UpperCamelCase				):  # noqa: B017
               t.put(1				)




   def _lowerCAmelCase   (self			:int				)->      None:
         __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(_UpperCamelCase				):  # noqa: B017
               t.search(2				)




   def _lowerCAmelCase   (self			:Dict				)->      None:
         __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 _lowerCAmelCase   (self			:int				)->      None:
         __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 _lowerCAmelCase   (self			:Optional[int]				)->      None:
         __A      =       self._get_binary_search_tree()
         t.empty()
         assert t.root is None




   def _lowerCAmelCase   (self			:List[str]				)->      None:
         __A      =       self._get_binary_search_tree()
         assert not t.is_empty()

         t.empty()
         assert t.is_empty()




   def _lowerCAmelCase   (self			:List[Any]				)->      None:
         __A      =       self._get_binary_search_tree()

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




   def _lowerCAmelCase   (self			:Tuple				)->      None:
         __A      =       self._get_binary_search_tree()

         assert t.get_max_label() == 14

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




   def _lowerCAmelCase   (self			:int				)->      None:
         __A      =       self._get_binary_search_tree()

         assert t.get_min_label() == 1

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




   def _lowerCAmelCase   (self			:Any				)->      None:
         __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 _lowerCAmelCase   (self			:Tuple				)->      None:
         __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       (			)			->		None:







      '''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(
          '''
            8
           / \\
          3   10
         / \\    \\
        1   6    14
           / \\   /
          4   7 13
           \\
            5
        '''				)

      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:'''      ,       lowerCamelCase				)

      # Prints all the elements of the list in preorder traversal
      __A      =       [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(
          '''
          4
         / \\
        1   7
             \\
              5
        '''				)
      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:'''      ,       lowerCamelCase				)

      # 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:'''      ,       lowerCamelCase				)

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


if __name__ == "__main__":
       binary_search_tree_example()












from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_tf_available, is_torch_available


snake_case__      :							Optional[int]									=  {'configuration_cvt': ['CVT_PRETRAINED_CONFIG_ARCHIVE_MAP', 'CvtConfig']}


try:
       if not is_torch_available():
              raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
       pass
else:
       snake_case__      :							Union[str, Any]									=  [
           'CVT_PRETRAINED_MODEL_ARCHIVE_LIST',
           'CvtForImageClassification',
           'CvtModel',
           'CvtPreTrainedModel',
       ]

try:
       if not is_tf_available():
              raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
       pass
else:
       snake_case__      :							List[str]									=  [
           'TF_CVT_PRETRAINED_MODEL_ARCHIVE_LIST',
           'TFCvtForImageClassification',
           'TFCvtModel',
           'TFCvtPreTrainedModel',
       ]

if TYPE_CHECKING:
       from .configuration_cvt import CVT_PRETRAINED_CONFIG_ARCHIVE_MAP, CvtConfig

       try:
              if not is_torch_available():
                     raise OptionalDependencyNotAvailable()
       except OptionalDependencyNotAvailable:
              pass
       else:
              from .modeling_cvt import (
                  CVT_PRETRAINED_MODEL_ARCHIVE_LIST,
                  CvtForImageClassification,
                  CvtModel,
                  CvtPreTrainedModel,
              )

       try:
              if not is_tf_available():
                     raise OptionalDependencyNotAvailable()
       except OptionalDependencyNotAvailable:
              pass
       else:
              from .modeling_tf_cvt import (
                  TF_CVT_PRETRAINED_MODEL_ARCHIVE_LIST,
                  TFCvtForImageClassification,
                  TFCvtModel,
                  TFCvtPreTrainedModel,
              )


else:
       import sys

       snake_case__      :							Dict									=  _LazyModule(__name__, globals()['__file__'], _import_structure, module_spec=__spec__)





