


from __future__ import annotations

import unittest
from collections.abc import Iterator
class 	a__				:





			'''simple docstring'''

			def __init__(     self       : List[Any] ,						lowerCAmelCase_       : Tuple ,						lowerCAmelCase_       : Dict  )			->		Tuple:
						__A=  label
						__A=  parent
						__A=  None
						__A=  None


class 	a__				:





			'''simple docstring'''

			def __init__(     self       : Optional[Any]  )			->		Optional[Any]:
						__A=  None
			def 				lowerCAmelCase    (     self       : str  )			->		int:
						__A=  None
			def 				lowerCAmelCase    (     self       : Dict  )			->		List[str]:
						return self.root is None
			def 				lowerCAmelCase    (     self       : List[str] ,						lowerCAmelCase_       : Dict  )			->		List[Any]:
						__A=  self._put(self.root ,						__UpperCamelCase  )
			def 				lowerCAmelCase    (     self       : Union[str, Any] ,						lowerCAmelCase_       : Union[str, Any] ,						lowerCAmelCase_       : Union[str, Any] ,						lowerCAmelCase_       : List[str] = None  )			->		Any:
						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       : int ,						lowerCAmelCase_       : Optional[Any]  )			->		Any:
						return self._search(self.root ,						__UpperCamelCase  )
			def 				lowerCAmelCase    (     self       : Optional[Any] ,						lowerCAmelCase_       : int ,						lowerCAmelCase_       : List[str]  )			->		List[str]:
						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       : Optional[int] ,						lowerCAmelCase_       : Tuple  )			->		Union[str, Any]:
						__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       : Dict ,						lowerCAmelCase_       : Optional[Any] ,						lowerCAmelCase_       : Dict  )			->		Any:
						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       : Dict ,						lowerCAmelCase_       : Dict  )			->		Optional[Any]:
						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       : Union[str, Any] ,						lowerCAmelCase_       : List[str]  )			->		Dict:
						try:
									self.search(__UpperCamelCase  )
									return True
						except Exception:
									return False
			def 				lowerCAmelCase    (     self       : Tuple  )			->		Union[str, Any]:
						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       : str  )			->		Optional[Any]:
						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       : Optional[int]  )			->		Optional[Any]:
						return self._inorder_traversal(self.root  )
			def 				lowerCAmelCase    (     self       : Tuple ,						lowerCAmelCase_       : Tuple  )			->		str:
						if node is not None:
									yield from self._inorder_traversal(node.left  )
									yield node
									yield from self._inorder_traversal(node.right  )
			def 				lowerCAmelCase    (     self       : Optional[Any]  )			->		str:
						return self._preorder_traversal(self.root  )

			def 				lowerCAmelCase    (     self       : Union[str, Any] ,						lowerCAmelCase_       : Tuple  )			->		Tuple:
						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 				lowerCAmelCase    (     )			->		Dict:
						__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  )			->		Any:
						__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       : Optional[Any]  )			->		Tuple:
						__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  )			->		Dict:
						__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  )			->		Optional[int]:
						__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       : Any  )			->		int:
						__A=  self._get_binary_search_tree()
						t.empty()
						assert t.root is None
			def 				lowerCAmelCase    (     self       : List[Any]  )			->		List[str]:
						__A=  self._get_binary_search_tree()
						assert not t.is_empty()

						t.empty()
						assert t.is_empty()
			def 				lowerCAmelCase    (     self       : Optional[int]  )			->		Optional[Any]:
						__A=  self._get_binary_search_tree()

						assert t.exists(6  )
						assert not t.exists(-1  )
			def 				lowerCAmelCase    (     self       : Dict  )			->		int:
						__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       : List[Any]  )			->		Optional[Any]:
						__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       : Tuple  )			->		Dict:
						__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       : Optional[Any]  )			->		Tuple:
						__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 	UpperCAmelCase__(							):






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

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

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

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

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


if __name__ == "__main__":
					binary_search_tree_example()







'''simple docstring'''





from typing import Any
class 	a__				:





			'''simple docstring'''

			def __init__(     self       : Any  )			->		int:
						__A=  []
						__A=  0
			def __str__(     self       : Tuple  )			->		Dict:
						__A=  '<' + str(self.stack  )[1:-1] + '>'
						return printed
			def 				lowerCAmelCase    (     self       : Tuple ,						lowerCAmelCase_       : Any  )			->		None:
						self.stack.append(lowerCAmelCase_  )
						__A=  self.length + 1
			def 				lowerCAmelCase    (     self       : int  )			->		Any:
						self.rotate(1  )
						__A=  self.stack[self.length - 1]
						__A=  self.stack[:-1]
						self.rotate(self.length - 1  )
						__A=  self.length - 1
						return dequeued
			def 				lowerCAmelCase    (     self       : Optional[int] ,						lowerCAmelCase_       : int  )			->		None:
						for _ in range(lowerCAmelCase_  ):
									__A=  self.stack[0]
									__A=  self.stack[1:]
									self.put(lowerCAmelCase_  )
									__A=  self.length - 1
			def 				lowerCAmelCase    (     self       : Tuple  )			->		Any:
						__A=  self.get()
						self.put(lowerCAmelCase_  )
						self.rotate(self.length - 1  )
						return front
			def 				lowerCAmelCase    (     self       : Dict  )			->		int:
						return self.length



