




from __future__ import annotations

import unittest
from collections.abc import Iterator


class       SCREAMING_SNAKE_CASE_							:



	"""simple docstring"""


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







						"""simple docstring"""







						__UpperCamelCase				:  List[Any]								=			label
						__UpperCamelCase				:  int								=			parent
						__UpperCamelCase				:  Optional[Any]								=			None
						__UpperCamelCase				:  List[str]								=			None







class       SCREAMING_SNAKE_CASE_							:



	"""simple docstring"""


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







						"""simple docstring"""







						__UpperCamelCase				:  Optional[Any]								=			None






	def 				lowerCamelCase__    (				self		:	Dict  )  ->					Tuple:







						"""simple docstring"""







						__UpperCamelCase				:  Union[str, Any]								=			None






	def 				lowerCamelCase__    (				self		:	Tuple  )  ->					List[Any]:







						"""simple docstring"""







						return self.root is None






	def 				lowerCamelCase__    (				self		:	List[str]				,    lowerCAmelCase		:	Union[str, Any]  )  ->					List[Any]:







						"""simple docstring"""







						__UpperCamelCase				:  Dict								=			self._put(self.root				,    __UpperCamelCase  )






	def 				lowerCamelCase__    (				self		:	Union[str, Any]				,    lowerCAmelCase		:	Any				,    lowerCAmelCase		:	Dict				,    lowerCAmelCase		:	Tuple = None  )  ->					Union[str, Any]:







						"""simple docstring"""







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

						return node






	def 				lowerCamelCase__    (				self		:	List[str]				,    lowerCAmelCase		:	str  )  ->					Optional[Any]:







						"""simple docstring"""







						return self._search(self.root				,    __UpperCamelCase  )






	def 				lowerCamelCase__    (				self		:	Any				,    lowerCAmelCase		:	Tuple				,    lowerCAmelCase		:	Optional[Any]  )  ->					int:







						"""simple docstring"""







						if node is None:
											__UpperCamelCase				:  Union[str, Any]								=			F'''Node with label {label} does not exist'''
											raise Exception(__UpperCamelCase  )
						else:
											if label < node.label:
																__UpperCamelCase				:  Tuple								=			self._search(node.left				,    __UpperCamelCase  )
											elif label > node.label:
																__UpperCamelCase				:  int								=			self._search(node.right				,    __UpperCamelCase  )

						return node






	def 				lowerCamelCase__    (				self		:	Union[str, Any]				,    lowerCAmelCase		:	int  )  ->					Tuple:







						"""simple docstring"""







						__UpperCamelCase				:  Optional[int]								=			self.search(__UpperCamelCase  )
						if node.right and node.left:
											__UpperCamelCase				:  Optional[int]								=			self._get_lowest_node(node.right  )
											__UpperCamelCase				:  Union[str, Any]								=			node.left
											__UpperCamelCase				:  str								=			node.right
											__UpperCamelCase				:  Tuple								=			lowest_node
											if node.right:
																__UpperCamelCase				:  Tuple								=			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		:	Optional[Any]				,    lowerCAmelCase		:	str				,    lowerCAmelCase		:	Tuple  )  ->					Optional[Any]:







						"""simple docstring"""







						if new_children:
											__UpperCamelCase				:  Any								=			node.parent

						if node.parent:
											if node.parent.right == node:
																__UpperCamelCase				:  Any								=			new_children
											else:
																__UpperCamelCase				:  str								=			new_children
						else:
											__UpperCamelCase				:  int								=			new_children






	def 				lowerCamelCase__    (				self		:	List[str]				,    lowerCAmelCase		:	Optional[Any]  )  ->					int:







						"""simple docstring"""







						if node.left:
											__UpperCamelCase				:  Any								=			self._get_lowest_node(node.left  )
						else:
											__UpperCamelCase				:  str								=			node
											self._reassign_nodes(__UpperCamelCase				,    node.right  )

						return lowest_node






	def 				lowerCamelCase__    (				self		:	Any				,    lowerCAmelCase		:	Any  )  ->					List[Any]:







						"""simple docstring"""







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






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







						"""simple docstring"""







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

						__UpperCamelCase				:  Optional[Any]								=			self.root
						while node.right is not None:
											__UpperCamelCase				:  Dict								=			node.right

						return node.label






	def 				lowerCamelCase__    (				self		:	Optional[Any]  )  ->					Tuple:







						"""simple docstring"""







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

						__UpperCamelCase				:  int								=			self.root
						while node.left is not None:
											__UpperCamelCase				:  Optional[Any]								=			node.left

						return node.label






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







						"""simple docstring"""







						return self._inorder_traversal(self.root  )






	def 				lowerCamelCase__    (				self		:	Dict				,    lowerCAmelCase		:	Optional[int]  )  ->					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 				lowerCamelCase__    (				self		:	Tuple  )  ->					int:







						"""simple docstring"""







						return self._preorder_traversal(self.root  )






	def 				lowerCamelCase__    (				self		:	Tuple				,    lowerCAmelCase		:	Tuple  )  ->					Optional[int]:







						"""simple docstring"""







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







class       SCREAMING_SNAKE_CASE_							(					unittest.TestCase      ):



	"""simple docstring"""


	@staticmethod
	def 				lowerCamelCase__    (				)  ->					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 				lowerCamelCase__    (				self		:	Optional[int]  )  ->					Any:







						"""simple docstring"""







						__UpperCamelCase				:  List[Any]								=			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		:	Union[str, Any]  )  ->					Optional[int]:







						"""simple docstring"""







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

						__UpperCamelCase				:  Optional[int]								=			t.search(6  )
						assert node.label == 6

						__UpperCamelCase				:  int								=			t.search(13  )
						assert node.label == 13

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






	def 				lowerCamelCase__    (				self		:	Any  )  ->					Optional[int]:







						"""simple docstring"""







						__UpperCamelCase				:  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 				lowerCamelCase__    (				self		:	Dict  )  ->					List[Any]:







						"""simple docstring"""







						__UpperCamelCase				:  Dict								=			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		:	Union[str, Any]  )  ->					str:







						"""simple docstring"""







						__UpperCamelCase				:  Tuple								=			self._get_binary_search_tree()
						t.empty()
						assert t.root is None






	def 				lowerCamelCase__    (				self		:	Tuple  )  ->					int:







						"""simple docstring"""







						__UpperCamelCase				:  Any								=			self._get_binary_search_tree()
						assert not t.is_empty()

						t.empty()
						assert t.is_empty()






	def 				lowerCamelCase__    (				self		:	List[Any]  )  ->					Optional[Any]:







						"""simple docstring"""







						__UpperCamelCase				:  int								=			self._get_binary_search_tree()

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






	def 				lowerCamelCase__    (				self		:	str  )  ->					int:







						"""simple docstring"""







						__UpperCamelCase				:  int								=			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  )  ->					List[Any]:







						"""simple docstring"""







						__UpperCamelCase				:  List[str]								=			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		:	Optional[int]  )  ->					List[Any]:







						"""simple docstring"""







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

						__UpperCamelCase				:  str								=			[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		:	int  )  ->					Union[str, Any]:







						"""simple docstring"""







						__UpperCamelCase				:  int								=			self._get_binary_search_tree()

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







def 							A__   ()    ->	List[Any]:
					__UpperCamelCase				:  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
					__UpperCamelCase				:  int								=			[i.label for i in t.inorder_traversal()]
					print("""Inorder traversal:"""		,  lowercase_							)

					# Prints all the elements of the list in preorder traversal
					__UpperCamelCase				:  List[Any]								=			[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
					__UpperCamelCase				:  Dict								=			[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
					__UpperCamelCase				:  Any								=			[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()












a__		    =    {
    "kilogram": 1,
    "gram": pow(10, 3),
    "milligram": pow(10, 6),
    "metric-ton": pow(10, -3),
    "long-ton": 0.00_0984_2073,
    "short-ton": 0.00_1102_3122,
    "pound": 2.20_4624_4202,
    "stone": 0.15_7473_1728,
    "ounce": 35.2_7399_0723,
    "carrat": 5000,
    "atomic-mass-unit": 6.0_2213_6652e26,
}

a__		    =    {
    "kilogram": 1,
    "gram": pow(10, -3),
    "milligram": pow(10, -6),
    "metric-ton": pow(10, 3),
    "long-ton": 1016.0_4608,
    "short-ton": 907.184,
    "pound": 0.45_3592,
    "stone": 6.3_5029,
    "ounce": 0.028_3495,
    "carrat": 0.0002,
    "atomic-mass-unit": 1.6_6054_0199e-27,
}





def 							A__   (snake_case      :		str		,  snake_case      :		str		,  snake_case      :		float							)    ->	float:
					if to_type not in KILOGRAM_CHART or from_type not in WEIGHT_TYPE_CHART:
										__UpperCamelCase				:  Any								=			(
										    F'''Invalid \'from_type\' or \'to_type\' value: {from_type!r}, {to_type!r}\n'''
										    F'''Supported values are: {", ".join(snake_case							)}'''
										)
										raise ValueError(snake_case							)
					return value * KILOGRAM_CHART[to_type] * WEIGHT_TYPE_CHART[from_type]


if __name__ == "__main__":
	import doctest

	doctest.testmod()






