



from __future__ import annotations

import unittest
from collections.abc import Iterator


class 	lowerCamelCase__ :


						def __init__( self						:  Union[str, Any]      ,       _a						:  int      ,       _a						:  Node | None			):
													a__:       Optional[int]											=label
													a__:       Tuple											=parent
													a__:       Dict											=None
													a__:       Optional[int]											=None


class 	lowerCamelCase__ :


						def __init__( self						:  Dict			):
													a__:       Any											=None


						def   _lowerCamelCase			( self						:  str			):
													a__:       Optional[Any]											=None


						def   _lowerCamelCase			( self						:  Optional[int]			):
													return self.root is None


						def   _lowerCamelCase			( self						:  Optional[Any]      ,       _a						:  int			):
													a__:       Union[str, Any]											=self._put(self.root      ,       _a			)


						def   _lowerCamelCase			( self						:  Optional[Any]      ,       _a						:  Node | None      ,       _a						:  int      ,       _a						:  Node | None = None			):







													if node is None:
																				a__:       Optional[int]											=Node(_a      ,       _a			)
													else:
																				if label < node.label:
																											a__:       List[Any]											=self._put(node.left      ,       _a      ,       _a			)
																				elif label > node.label:
																											a__:       List[str]											=self._put(node.right      ,       _a      ,       _a			)
																				else:
																											a__:       Optional[int]											=F"Node with label {label} already exists"
																											raise Exception(_a			)

													return node


						def   _lowerCamelCase			( self						:  Tuple      ,       _a						:  int			):
													return self._search(self.root      ,       _a			)


						def   _lowerCamelCase			( self						:  List[str]      ,       _a						:  Node | None      ,       _a						:  int			):







													if node is None:
																				a__:       List[Any]											=F"Node with label {label} does not exist"
																				raise Exception(_a			)
													else:
																				if label < node.label:
																											a__:       str											=self._search(node.left      ,       _a			)
																				elif label > node.label:
																											a__:       Any											=self._search(node.right      ,       _a			)

													return node


						def   _lowerCamelCase			( self						:  Any      ,       _a						:  int			):
													a__:       Any											=self.search(_a			)
													if node.right and node.left:
																				a__:       Dict											=self._get_lowest_node(node.right			)
																				a__:       Union[str, Any]											=node.left
																				a__:       Tuple											=node.right
																				a__:       Union[str, Any]											=lowest_node
																				if node.right:
																											a__:       Optional[int]											=lowest_node
																				self._reassign_nodes(_a      ,       _a			)
													elif not node.right and node.left:
																				self._reassign_nodes(_a      ,       node.left			)
													elif node.right and not node.left:
																				self._reassign_nodes(_a      ,       node.right			)
													else:
																				self._reassign_nodes(_a      ,       _a			)


						def   _lowerCamelCase			( self						:  Tuple      ,       _a						:  Node      ,       _a						:  Node | None			):







													if new_children:
																				a__:       Union[str, Any]											=node.parent

													if node.parent:
																				if node.parent.right == node:
																											a__:       int											=new_children
																				else:
																											a__:       List[str]											=new_children
													else:
																				a__:       str											=new_children


						def   _lowerCamelCase			( self						:  int      ,       _a						:  Node			):







													if node.left:
																				a__:       Optional[int]											=self._get_lowest_node(node.left			)
													else:
																				a__:       str											=node
																				self._reassign_nodes(_a      ,       node.right			)

													return lowest_node


						def   _lowerCamelCase			( self						:  int      ,       _a						:  int			):







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


						def   _lowerCamelCase			( self						:  Union[str, Any]			):







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

													a__:       int											=self.root
													while node.right is not None:
																				a__:       List[Any]											=node.right

													return node.label


						def   _lowerCamelCase			( self						:  Union[str, Any]			):







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

													a__:       List[str]											=self.root
													while node.left is not None:
																				a__:       Optional[int]											=node.left

													return node.label


						def   _lowerCamelCase			( self						:  List[Any]			):
													return self._inorder_traversal(self.root			)


						def   _lowerCamelCase			( self						:  str      ,       _a						:  Node | None			):







													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]			):
													return self._preorder_traversal(self.root			)







						def   _lowerCamelCase			( self						:  Any      ,       _a						:  Node | None			):







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


class 	lowerCamelCase__ (		unittest.TestCase   ):


						@staticmethod
						def   _lowerCamelCase			( ):
													a__:       Tuple											=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			)

													return t


						def   _lowerCamelCase			( self						:  Dict			):
													a__:       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(1_0			)
													assert t.root.right is not None
													assert t.root.right.parent == t.root
													assert t.root.right.label == 1_0

													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(_a			):  # noqa: B017
																				t.put(1			)


						def   _lowerCamelCase			( self						:  Tuple			):
													a__:       Optional[Any]											=self._get_binary_search_tree()

													a__:       List[str]											=t.search(6			)
													assert node.label == 6

													a__:       List[str]											=t.search(1_3			)
													assert node.label == 1_3

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


						def   _lowerCamelCase			( self						:  Any			):
													a__:       List[Any]											=self._get_binary_search_tree()

													t.remove(1_3			)
													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			):
													a__:       Any											=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						:  int			):
													a__:       List[Any]											=self._get_binary_search_tree()
													t.empty()
													assert t.root is None


						def   _lowerCamelCase			( self						:  str			):
													a__:       Tuple											=self._get_binary_search_tree()
													assert not t.is_empty()

													t.empty()
													assert t.is_empty()


						def   _lowerCamelCase			( self						:  Any			):
													a__:       List[Any]											=self._get_binary_search_tree()

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


						def   _lowerCamelCase			( self						:  List[str]			):
													a__:       List[str]											=self._get_binary_search_tree()

													assert t.get_max_label() == 1_4

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


						def   _lowerCamelCase			( self						:  Optional[int]			):
													a__:       Optional[int]											=self._get_binary_search_tree()

													assert t.get_min_label() == 1

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


						def   _lowerCamelCase			( self						:  Optional[int]			):
													a__:       Tuple											=self._get_binary_search_tree()

													a__:       Tuple											=[i.label for i in t.inorder_traversal()]
													assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 1_0, 1_3, 1_4]







						def   _lowerCamelCase			( self						:  List[Any]			):
													a__:       str											=self._get_binary_search_tree()

													a__:       List[str]											=[i.label for i in t.preorder_traversal()]
													assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 1_0, 1_4, 1_3]





def 						__lowerCamelCase       (      ):
							a__:       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						)

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

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

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

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

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


if __name__ == "__main__":
		binary_search_tree_example()











def 						__lowerCamelCase       (      __magic_name__	:  list     , __magic_name__	:  int						):
							for index, item in enumerate(__magic_name__						):
														if item == target:
																					return index
							return -1





def 						__lowerCamelCase       (      __magic_name__	:  list     , __magic_name__	:  int     , __magic_name__	:  int     , __magic_name__	:  int						):
							if not (0 <= high < len(__magic_name__						) and 0 <= low < len(__magic_name__						)):
														raise Exception("Invalid upper or lower bound!"						)
							if high < low:
														return -1
							if sequence[low] == target:
														return low
							if sequence[high] == target:
														return high
							return rec_linear_search(__magic_name__     , low + 1     , high - 1     , __magic_name__						)


if __name__ == "__main__":
		__UpperCAmelCase						  =     input('''Enter numbers separated by comma:\n''').strip()
		__UpperCAmelCase						  =     [int(item.strip()) for item in user_input.split(''',''')]

		__UpperCAmelCase						  =     int(input('''Enter a single number to be found in the list:\n''').strip())
		__UpperCAmelCase						  =     linear_search(sequence, target)
		if result != -1:
				print(f"""linear_search({sequence}, {target}) = {result}""")
		else:
				print(f"""{target} was not found in {sequence}""")





