

from __future__ import annotations

import unittest
from collections.abc import Iterator

class 						__snake_case						:
							"""simple docstring"""







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






														"""simple docstring"""


														__snake_case					  =       label
														__snake_case					  =       parent
														__snake_case					  =       None
														__snake_case					  =       None






class 						__snake_case						:
							"""simple docstring"""







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






														"""simple docstring"""


														__snake_case					  =       None


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






														"""simple docstring"""


														__snake_case					  =       None


							def  a		(		self      )			->       List[Any]:






														"""simple docstring"""


														return self.root is None


							def  a		(		self			,   _UpperCamelCase      )			->       Any:






														"""simple docstring"""


														__snake_case					  =       self._put(self.root			,   _lowerCamelCase      )


							def  a		(		self			,   _UpperCamelCase			,   _UpperCamelCase			,   _UpperCamelCase = None      )			->       Union[str, Any]:






														"""simple docstring"""


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

														return node


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






														"""simple docstring"""


														return self._search(self.root			,   _lowerCamelCase      )


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






														"""simple docstring"""


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

														return node


							def  a		(		self			,   _UpperCamelCase      )			->       Any:






														"""simple docstring"""


														__snake_case					  =       self.search(_lowerCamelCase      )
														if node.right and node.left:
																					__snake_case					  =       self._get_lowest_node(node.right      )
																					__snake_case					  =       node.left
																					__snake_case					  =       node.right
																					__snake_case					  =       lowest_node
																					if node.right:
																												__snake_case					  =       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  a		(		self			,   _UpperCamelCase			,   _UpperCamelCase      )			->       Any:






														"""simple docstring"""


														if new_children:
																					__snake_case					  =       node.parent

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


							def  a		(		self			,   _UpperCamelCase      )			->       Tuple:






														"""simple docstring"""


														if node.left:
																					__snake_case					  =       self._get_lowest_node(node.left      )
														else:
																					__snake_case					  =       node
																					self._reassign_nodes(_lowerCamelCase			,   node.right      )

														return lowest_node


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






														"""simple docstring"""


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


							def  a		(		self      )			->       Tuple:






														"""simple docstring"""


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

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

														return node.label


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






														"""simple docstring"""


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

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

														return node.label


							def  a		(		self      )			->       Tuple:






														"""simple docstring"""


														return self._inorder_traversal(self.root      )


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






														"""simple docstring"""


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


							def  a		(		self      )			->       Tuple:






														"""simple docstring"""


														return self._preorder_traversal(self.root      )






							def  a		(		self			,   _UpperCamelCase      )			->       str:






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







							@staticmethod
							def  a		(		)			->       Optional[int]:






														"""simple docstring"""


														__snake_case					  =       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  a		(		self      )			->       List[Any]:






														"""simple docstring"""


														__snake_case					  =       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  a		(		self      )			->       List[str]:






														"""simple docstring"""


														__snake_case					  =       self._get_binary_search_tree()

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

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

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


							def  a		(		self      )			->       Dict:






														"""simple docstring"""


														__snake_case					  =       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  a		(		self      )			->       Dict:






														"""simple docstring"""


														__snake_case					  =       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  a		(		self      )			->       List[Any]:






														"""simple docstring"""


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


							def  a		(		self      )			->       Dict:






														"""simple docstring"""


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

														t.empty()
														assert t.is_empty()


							def  a		(		self      )			->       List[str]:






														"""simple docstring"""


														__snake_case					  =       self._get_binary_search_tree()

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


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






														"""simple docstring"""


														__snake_case					  =       self._get_binary_search_tree()

														assert t.get_max_label() == 14

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


							def  a		(		self      )			->       str:






														"""simple docstring"""


														__snake_case					  =       self._get_binary_search_tree()

														assert t.get_min_label() == 1

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


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






														"""simple docstring"""


														__snake_case					  =       self._get_binary_search_tree()

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






							def  a		(		self      )			->       str:






														"""simple docstring"""


														__snake_case					  =       self._get_binary_search_tree()

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







def 	lowerCamelCase__			(   ):


							"""simple docstring"""




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

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

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

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

							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_tokenizers_available, is_torch_available


UpperCamelCase__		   =    {
    '''configuration_splinter''': ['''SPLINTER_PRETRAINED_CONFIG_ARCHIVE_MAP''', '''SplinterConfig'''],
    '''tokenization_splinter''': ['''SplinterTokenizer'''],
}

try:
    if not is_tokenizers_available():
        raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
    pass
else:
    UpperCamelCase__		   =    ['''SplinterTokenizerFast''']

try:
    if not is_torch_available():
        raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
    pass
else:
    UpperCamelCase__		   =    [
        '''SPLINTER_PRETRAINED_MODEL_ARCHIVE_LIST''',
        '''SplinterForQuestionAnswering''',
        '''SplinterForPreTraining''',
        '''SplinterLayer''',
        '''SplinterModel''',
        '''SplinterPreTrainedModel''',
    ]


if TYPE_CHECKING:
    from .configuration_splinter import SPLINTER_PRETRAINED_CONFIG_ARCHIVE_MAP, SplinterConfig
    from .tokenization_splinter import SplinterTokenizer

    try:
        if not is_tokenizers_available():
            raise OptionalDependencyNotAvailable()
    except OptionalDependencyNotAvailable:
        pass
    else:
        from .tokenization_splinter_fast import SplinterTokenizerFast

    try:
        if not is_torch_available():
            raise OptionalDependencyNotAvailable()
    except OptionalDependencyNotAvailable:
        pass
    else:
        from .modeling_splinter import (
            SPLINTER_PRETRAINED_MODEL_ARCHIVE_LIST,
            SplinterForPreTraining,
            SplinterForQuestionAnswering,
            SplinterLayer,
            SplinterModel,
            SplinterPreTrainedModel,
        )


else:
    import sys

    UpperCamelCase__		   =    _LazyModule(__name__, globals()['''__file__'''], _import_structure, module_spec=__spec__)

