

"""simple docstring"""






from collections.abc import Iterable
from typing import Any






class      _UpperCAmelCase      :
			def __init__(		self   ,		_A = None  )     ->     int:






				'''simple docstring'''







				_UpperCAmelCase     :				Optional[Any]          =       value
				_UpperCAmelCase     :				Optional[Any]          =       None  # Added in order to delete a node easier
				_UpperCAmelCase     :				Tuple          =       None
				_UpperCAmelCase     :				Optional[Any]          =       None
			def __repr__(		self  )     ->     Optional[Any]:






				'''simple docstring'''







				from pprint import pformat

				if self.left is None and self.right is None:
					return str(self.value  )
				return pformat({f'''{self.value}''': (self.left, self.right)}   ,		indent=1  )






class      _UpperCAmelCase      :
			def __init__(		self   ,		_A = None  )     ->     Optional[Any]:






				'''simple docstring'''







				_UpperCAmelCase     :				Dict          =       root
			def __str__(		self  )     ->     str:






				'''simple docstring'''







				return str(self.root  )
			def 				__snake_case			(		self   ,		_A   ,		_A  )     ->     int:






				'''simple docstring'''







				if new_children is not None:  # reset its kids
					_UpperCAmelCase     :				List[str]          =       node.parent
				if node.parent is not None:  # reset its parent
					if self.is_right(_lowerCamelCase  ):  # If it is the right children
						_UpperCAmelCase     :				int          =       new_children
					else:
						_UpperCAmelCase     :				int          =       new_children
				else:
					_UpperCAmelCase     :				int          =       new_children
			def 				__snake_case			(		self   ,		_A  )     ->     Dict:






				'''simple docstring'''







				if node.parent and node.parent.right:
					return node == node.parent.right
				return False
			def 				__snake_case			(		self  )     ->     Dict:






				'''simple docstring'''







				return self.root is None
			def 				__snake_case			(		self   ,		_A  )     ->     Dict:






				'''simple docstring'''







				_UpperCAmelCase     :				int          =       Node(_lowerCamelCase  )  # create a new Node
				if self.empty():  # if Tree is empty
					_UpperCAmelCase     :				Union[str, Any]          =       new_node  # set its root
				else:  # Tree is not empty
					_UpperCAmelCase     :				Optional[Any]          =       self.root  # from root
					if parent_node is None:
						return
					while True:  # While we don't get to a leaf
						if value < parent_node.value:  # We go left
							if parent_node.left is None:
								_UpperCAmelCase     :				Optional[Any]          =       new_node  # We insert the new node in a leaf
								break
							else:
								_UpperCAmelCase     :				Tuple          =       parent_node.left
						else:
							if parent_node.right is None:
								_UpperCAmelCase     :				int          =       new_node
								break
							else:
								_UpperCAmelCase     :				List[Any]          =       parent_node.right
					_UpperCAmelCase     :				int          =       parent_node
			def 				__snake_case			(		self   ,		*_A  )     ->     List[str]:






				'''simple docstring'''







				for value in values:
					self.__insert(_lowerCamelCase  )
			def 				__snake_case			(		self   ,		_A  )     ->     str:






				'''simple docstring'''







				if self.empty():
					raise IndexError("""Warning: Tree is empty! please use another."""  )
				else:
					_UpperCAmelCase     :				str          =       self.root
					# use lazy evaluation here to avoid NoneType Attribute error
					while node is not None and node.value is not value:
						_UpperCAmelCase     :				Optional[int]          =       node.left if value < node.value else node.right
					return node
			def 				__snake_case			(		self   ,		_A = None  )     ->     List[Any]:






				'''simple docstring'''







				if node is None:
					if self.root is None:
						return None
					_UpperCAmelCase     :				Union[str, Any]          =       self.root

				if not self.empty():
					while node.right is not None:
						_UpperCAmelCase     :				Any          =       node.right
				return node
			def 				__snake_case			(		self   ,		_A = None  )     ->     int:






				'''simple docstring'''







				if node is None:
					_UpperCAmelCase     :				Tuple          =       self.root
				if self.root is None:
					return None
				if not self.empty():
					_UpperCAmelCase     :				Optional[Any]          =       self.root
					while node.left is not None:
						_UpperCAmelCase     :				Any          =       node.left
				return node
			def 				__snake_case			(		self   ,		_A  )     ->     List[Any]:






				'''simple docstring'''







				_UpperCAmelCase     :				List[Any]          =       self.search(_lowerCamelCase  )  # Look for the node with that label
				if node is not None:
					if node.left is None and node.right is None:  # If it has no children
						self.__reassign_nodes(_lowerCamelCase   ,		_lowerCamelCase  )
					elif node.left is None:  # Has only right children
						self.__reassign_nodes(_lowerCamelCase   ,		node.right  )
					elif node.right is None:  # Has only left children
						self.__reassign_nodes(_lowerCamelCase   ,		node.left  )
					else:
						_UpperCAmelCase     :				Optional[Any]          =       self.get_max(
						    node.left  )  # Gets the max value of the left branch
						self.remove(tmp_node.value  )  # type: ignore
						_UpperCAmelCase     :				List[str]          =       (
						    tmp_node.value  # type: ignore
						)  # Assigns the value to the node to delete and keep tree structure
			def 				__snake_case			(		self   ,		_A  )     ->     str:






				'''simple docstring'''







				if node is not None:
					yield node  # Preorder Traversal
					yield from self.preorder_traverse(node.left  )
					yield from self.preorder_traverse(node.right  )
			def 				__snake_case			(		self   ,		_A=None  )     ->     Union[str, Any]:






				'''simple docstring'''







				if traversal_function is None:
					return self.preorder_traverse(self.root  )
				else:
					return traversal_function(self.root  )
			def 				__snake_case			(		self   ,		_A   ,		_A  )     ->     Optional[int]:






				'''simple docstring'''







				if node:
					self.inorder(_lowerCamelCase   ,		node.left  )
					arr.append(node.value  )
					self.inorder(_lowerCamelCase   ,		node.right  )
			def 				__snake_case			(		self   ,		_A   ,		_A  )     ->     Tuple:






				'''simple docstring'''







				_UpperCAmelCase     :				Optional[int]          =       []
				self.inorder(_lowerCamelCase   ,		_lowerCamelCase  )  # append all values to list using inorder traversal
				return arr[k - 1]
def    UpperCamelCase       (      _lowerCAmelCase  :    Optional[int]			)					->      list[Node]:
	_UpperCAmelCase     :				Dict          =       []
	if curr_node is not None:
		_UpperCAmelCase     :				List[str]          =       postorder(curr_node.left			) + postorder(curr_node.right			) + [curr_node]
	return node_list
def    UpperCamelCase       (      )					->      None:
	_UpperCAmelCase     :				Dict          =       (8, 3, 6, 1, 10, 14, 13, 4, 7)
	_UpperCAmelCase     :				Any          =       BinarySearchTree()
	for i in testlist:
		t.insert(__lowerCAmelCase			)

	# Prints all the elements of the list in order traversal
	print(__lowerCAmelCase			)

	if t.search(6			) is not None:
		print("""The value 6 exists"""			)
	else:
		print("""The value 6 doesn't exist"""			)

	if t.search(-1			) is not None:
		print("""The value -1 exists"""			)
	else:
		print("""The value -1 doesn't exist"""			)

	if not t.empty():
		print("""Max Value: """,	t.get_max().value			)  # type: ignore
		print("""Min Value: """,	t.get_min().value			)  # type: ignore

	for i in testlist:
		t.remove(__lowerCAmelCase			)
		print(__lowerCAmelCase			)


if __name__ == "__main__":
						import doctest

						doctest.testmod(verbose=True)






"""simple docstring"""


def      lowerCamelCase_					(   __lowerCAmelCase  ,       __lowerCAmelCase							)				->   float:




						'''simple docstring'''



						return price * (1 + tax_rate)


if __name__ == "__main__":
	print(F'''{price_plus_tax(100, 0.25) = }''')
	print(F'''{price_plus_tax(125.50, 0.05) = }''')


