"""simple docstring"""






from __future__ import annotations

import unittest
from collections.abc import Iterator






class     A:

		"""simple docstring"""





		def __init__(   self				,							SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__      )			->  int:

					"""simple docstring"""



					_UpperCamelCase				:List[Any]				    =  label
					_UpperCamelCase				:Dict				    =  parent
					_UpperCamelCase				:List[Any]				    =  None
					_UpperCamelCase				:int				    =  None






class     A:

		"""simple docstring"""





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

					"""simple docstring"""



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

					"""simple docstring"""



					_UpperCamelCase				:List[str]				    =  None
		def      _UpperCamelCase(   self      )			->  Tuple:

					"""simple docstring"""



					return self.root is None
		def      _UpperCamelCase(   self				,							SCREAMING_SNAKE_CASE__      )			->  Dict:

					"""simple docstring"""



					_UpperCamelCase				:Optional[int]				    =  self._put(self.root				,							__snake_case      )
		def      _UpperCamelCase(   self				,							SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__ = None      )			->  str:

					"""simple docstring"""



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

					return node
		def      _UpperCamelCase(   self				,							SCREAMING_SNAKE_CASE__      )			->  Any:

					"""simple docstring"""



					return self._search(self.root				,							__snake_case      )
		def      _UpperCamelCase(   self				,							SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__      )			->  int:

					"""simple docstring"""



					if node is None:
								_UpperCamelCase				:int				    =  f"Node with label {label} does not exist"
								raise Exception(__snake_case      )
					else:
								if label < node.label:
											_UpperCamelCase				:Dict				    =  self._search(node.left				,							__snake_case      )
								elif label > node.label:
											_UpperCamelCase				:Union[str, Any]				    =  self._search(node.right				,							__snake_case      )

					return node
		def      _UpperCamelCase(   self				,							SCREAMING_SNAKE_CASE__      )			->  Union[str, Any]:

					"""simple docstring"""



					_UpperCamelCase				:Any				    =  self.search(__snake_case      )
					if node.right and node.left:
								_UpperCamelCase				:Optional[Any]				    =  self._get_lowest_node(node.right      )
								_UpperCamelCase				:str				    =  node.left
								_UpperCamelCase				:Optional[Any]				    =  node.right
								_UpperCamelCase				:List[Any]				    =  lowest_node
								if node.right:
											_UpperCamelCase				:Tuple				    =  lowest_node
								self._reassign_nodes(__snake_case				,							__snake_case      )
					elif not node.right and node.left:
								self._reassign_nodes(__snake_case				,							node.left      )
					elif node.right and not node.left:
								self._reassign_nodes(__snake_case				,							node.right      )
					else:
								self._reassign_nodes(__snake_case				,							__snake_case      )
		def      _UpperCamelCase(   self				,							SCREAMING_SNAKE_CASE__				,							SCREAMING_SNAKE_CASE__      )			->  Dict:

					"""simple docstring"""



					if new_children:
								_UpperCamelCase				:Any				    =  node.parent

					if node.parent:
								if node.parent.right == node:
											_UpperCamelCase				:Tuple				    =  new_children
								else:
											_UpperCamelCase				:str				    =  new_children
					else:
								_UpperCamelCase				:Any				    =  new_children
		def      _UpperCamelCase(   self				,							SCREAMING_SNAKE_CASE__      )			->  Optional[int]:

					"""simple docstring"""



					if node.left:
								_UpperCamelCase				:Optional[Any]				    =  self._get_lowest_node(node.left      )
					else:
								_UpperCamelCase				:Tuple				    =  node
								self._reassign_nodes(__snake_case				,							node.right      )

					return lowest_node
		def      _UpperCamelCase(   self				,							SCREAMING_SNAKE_CASE__      )			->  List[Any]:

					"""simple docstring"""



					try:
								self.search(__snake_case      )
								return True
					except Exception:
								return False
		def      _UpperCamelCase(   self      )			->  Optional[int]:

					"""simple docstring"""



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

					_UpperCamelCase				:Optional[int]				    =  self.root
					while node.right is not None:
								_UpperCamelCase				:Any				    =  node.right

					return node.label
		def      _UpperCamelCase(   self      )			->  Optional[Any]:

					"""simple docstring"""



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

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

					return node.label
		def      _UpperCamelCase(   self      )			->  Union[str, Any]:

					"""simple docstring"""



					return self._inorder_traversal(self.root      )
		def      _UpperCamelCase(   self				,							SCREAMING_SNAKE_CASE__      )			->  List[Any]:

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

					"""simple docstring"""



					return self._preorder_traversal(self.root      )





		def      _UpperCamelCase(   self				,							SCREAMING_SNAKE_CASE__      )			->  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     A(     unittest.TestCase		):

		"""simple docstring"""





		@staticmethod
		def      _UpperCamelCase(   )			->  Union[str, Any]:

					"""simple docstring"""



					_UpperCamelCase				:List[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      _UpperCamelCase(   self      )			->  int:

					"""simple docstring"""



					_UpperCamelCase				:Tuple				    =  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(__snake_case      ):  # noqa: B017
								t.put(1      )
		def      _UpperCamelCase(   self      )			->  Union[str, Any]:

					"""simple docstring"""



					_UpperCamelCase				:Dict				    =  self._get_binary_search_tree()

					_UpperCamelCase				:Any				    =  t.search(6      )
					assert node.label == 6

					_UpperCamelCase				:str				    =  t.search(13      )
					assert node.label == 13

					with self.assertRaises(__snake_case      ):  # noqa: B017
								t.search(2      )
		def      _UpperCamelCase(   self      )			->  Optional[Any]:

					"""simple docstring"""



					_UpperCamelCase				:Optional[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      _UpperCamelCase(   self      )			->  List[str]:

					"""simple docstring"""



					_UpperCamelCase				:Tuple				    =  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      )			->  Dict:

					"""simple docstring"""



					_UpperCamelCase				:List[str]				    =  self._get_binary_search_tree()
					t.empty()
					assert t.root is None
		def      _UpperCamelCase(   self      )			->  str:

					"""simple docstring"""



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

					t.empty()
					assert t.is_empty()
		def      _UpperCamelCase(   self      )			->  str:

					"""simple docstring"""



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

					assert t.exists(6      )
					assert not t.exists(-1      )
		def      _UpperCamelCase(   self      )			->  List[Any]:

					"""simple docstring"""



					_UpperCamelCase				:Optional[Any]				    =  self._get_binary_search_tree()

					assert t.get_max_label() == 14

					t.empty()
					with self.assertRaises(__snake_case      ):  # noqa: B017
								t.get_max_label()
		def      _UpperCamelCase(   self      )			->  Tuple:

					"""simple docstring"""



					_UpperCamelCase				:Any				    =  self._get_binary_search_tree()

					assert t.get_min_label() == 1

					t.empty()
					with self.assertRaises(__snake_case      ):  # noqa: B017
								t.get_min_label()
		def      _UpperCamelCase(   self      )			->  Tuple:

					"""simple docstring"""



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

					_UpperCamelCase				:Union[str, 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      )			->  Optional[int]:

					"""simple docstring"""



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

					_UpperCamelCase				: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_					(   )				->     Tuple:
			_UpperCamelCase				:Optional[int]				    =  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
			_UpperCamelCase				:List[str]				    =  [i.label for i in t.inorder_traversal()]
			print('''Inorder traversal:'''					,				UpperCamelCase_		)

			# Prints all the elements of the list in preorder traversal
			_UpperCamelCase				:Tuple				    =  [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(
			    '''
          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
			_UpperCamelCase				:Dict				    =  [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
			_UpperCamelCase				:Optional[Any]				    =  [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_					(   snake_case__		)				->     str:
			_UpperCamelCase				:Tuple				    =  word.upper()
			_UpperCamelCase				:Dict				    =  0
			_UpperCamelCase				:Union[str, Any]				    =  {}
			_UpperCamelCase				:Optional[int]				    =  []

			for letter in word:
						if letter not in letter_nums:
									_UpperCamelCase				:Dict				    =  str(snake_case__		)
									next_num += 1
						word_pattern.append(letter_nums[letter]		)
			return ".".join(snake_case__		)


if __name__ == "__main__":
					import pprint
					import time

					UpperCamelCase__							:Dict       =  time.time()
					with open("""dictionary.txt""") as in_file:
										UpperCamelCase__							:str       =  in_file.read().splitlines()

					UpperCamelCase__							:dict       =  {}
					for word in word_list:
										UpperCamelCase__							:List[Any]       =  get_word_pattern(word)
										if pattern in all_patterns:
															all_patterns[pattern].append(word)
										else:
															UpperCamelCase__							:Tuple       =  [word]

					with open("""word_patterns.txt""", """w""") as out_file:
										out_file.write(pprint.pformat(all_patterns))

					UpperCamelCase__							:Dict       =  round(time.time() - start_time, 2)
					print(F"""Done!  {len(all_patterns):,} word patterns found in {total_time} seconds.""")
					# Done!  9,581 word patterns found in 0.58 seconds.

