


"""simple docstring"""






from collections.abc import Iterable
from typing import Any





class      lowerCamelCase__   :







					"""simple docstring"""


					def __init__(       self    : List[str] ,       UpperCamelCase    : int | None = None  ):
												'''simple docstring'''






												__UpperCAmelCase   :						Union[str, Any]      							=					value
												__UpperCAmelCase   :						Node | None      							=					None  # Added in order to delete a node easier
												__UpperCAmelCase   :						Node | None      							=					None
												__UpperCAmelCase   :						Node | None      							=					None






					def __repr__(       self    : int  ):
												'''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      lowerCamelCase__   :







					"""simple docstring"""


					def __init__(       self    : List[str] ,       UpperCamelCase    : Node | None = None  ):
												'''simple docstring'''






												__UpperCAmelCase   :						List[str]      							=					root






					def __str__(       self    : str  ):
												'''simple docstring'''






												return str(self.root  )






					def lowerCamelCase__							(       self    : Union[str, Any] ,       UpperCamelCase    : Node ,       UpperCamelCase    : Node | None  ):
												'''simple docstring'''






												if new_children is not None:  # reset its kids
																			__UpperCAmelCase   :						Any      							=					node.parent
												if node.parent is not None:  # reset its parent
																			if self.is_right(UpperCamelCase  ):  # If it is the right children
																										__UpperCAmelCase   :						str      							=					new_children
																			else:
																										__UpperCAmelCase   :						Optional[int]      							=					new_children
												else:
																			__UpperCAmelCase   :						Dict      							=					new_children






					def lowerCamelCase__							(       self    : Any ,       UpperCamelCase    : Node  ):
												'''simple docstring'''






												if node.parent and node.parent.right:
																			return node == node.parent.right
												return False






					def lowerCamelCase__							(       self    : int  ):
												'''simple docstring'''






												return self.root is None






					def lowerCamelCase__							(       self    : Tuple ,       UpperCamelCase    : Tuple  ):
												'''simple docstring'''






												__UpperCAmelCase   :						Optional[int]      							=					Node(UpperCamelCase  )  # create a new Node
												if self.empty():  # if Tree is empty
																			__UpperCAmelCase   :						int      							=					new_node  # set its root
												else:  # Tree is not empty
																			__UpperCAmelCase   :						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   :						Dict      							=					new_node  # We insert the new node in a leaf
																																								break
																																	else:
																																								__UpperCAmelCase   :						List[Any]      							=					parent_node.left
																										else:
																																	if parent_node.right is None:
																																								__UpperCAmelCase   :						Any      							=					new_node
																																								break
																																	else:
																																								__UpperCAmelCase   :						Any      							=					parent_node.right
																			__UpperCAmelCase   :						List[Any]      							=					parent_node






					def lowerCamelCase__							(       self    : Union[str, Any] ,       *UpperCamelCase    : Dict  ):
												'''simple docstring'''






												for value in values:
																			self.__insert(UpperCamelCase  )






					def lowerCamelCase__							(       self    : Any ,       UpperCamelCase    : str  ):
												'''simple docstring'''






												if self.empty():
																			raise IndexError("""Warning: Tree is empty! please use another."""  )
												else:
																			__UpperCAmelCase   :						Tuple      							=					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 lowerCamelCase__							(       self    : Dict ,       UpperCamelCase    : Node | None = None  ):
												'''simple docstring'''






												if node is None:
																			if self.root is None:
																										return None
																			__UpperCAmelCase   :						Optional[int]      							=					self.root

												if not self.empty():
																			while node.right is not None:
																										__UpperCAmelCase   :						List[str]      							=					node.right
												return node






					def lowerCamelCase__							(       self    : List[str] ,       UpperCamelCase    : Node | None = None  ):
												'''simple docstring'''






												if node is None:
																			__UpperCAmelCase   :						Optional[Any]      							=					self.root
												if self.root is None:
																			return None
												if not self.empty():
																			__UpperCAmelCase   :						Any      							=					self.root
																			while node.left is not None:
																										__UpperCAmelCase   :						Union[str, Any]      							=					node.left
												return node






					def lowerCamelCase__							(       self    : Optional[Any] ,       UpperCamelCase    : int  ):
												'''simple docstring'''






												__UpperCAmelCase   :						List[str]      							=					self.search(UpperCamelCase  )  # 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(UpperCamelCase ,       UpperCamelCase  )
																			elif node.left is None:  # Has only right children
																										self.__reassign_nodes(UpperCamelCase ,       node.right  )
																			elif node.right is None:  # Has only left children
																										self.__reassign_nodes(UpperCamelCase ,       node.left  )
																			else:
																										__UpperCAmelCase   :						List[str]      							=					self.get_max(
																										    node.left  )  # Gets the max value of the left branch
																										self.remove(tmp_node.value  )  # type: ignore
																										__UpperCAmelCase   :						Any      							=					(
																										    tmp_node.value  # type: ignore
																										)  # Assigns the value to the node to delete and keep tree structure






					def lowerCamelCase__							(       self    : Optional[Any] ,       UpperCamelCase    : Node | None  ):
												'''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 lowerCamelCase__							(       self    : int ,       UpperCamelCase    : Tuple=None  ):
												'''simple docstring'''






												if traversal_function is None:
																			return self.preorder_traverse(self.root  )
												else:
																			return traversal_function(self.root  )






					def lowerCamelCase__							(       self    : Union[str, Any] ,       UpperCamelCase    : list ,       UpperCamelCase    : Node | None  ):
												'''simple docstring'''






												if node:
																			self.inorder(UpperCamelCase ,       node.left  )
																			arr.append(node.value  )
																			self.inorder(UpperCamelCase ,       node.right  )






					def lowerCamelCase__							(       self    : Union[str, Any] ,       UpperCamelCase    : int ,       UpperCamelCase    : Node  ):
												'''simple docstring'''






												__UpperCAmelCase   :						list[int]      							=					[]
												self.inorder(UpperCamelCase ,       UpperCamelCase  )  # append all values to list using inorder traversal
												return arr[k - 1]






def      lowerCamelCase       (     _UpperCamelCase		:      Node | None							)		->       list[Node]:

							'''simple docstring'''



							__UpperCAmelCase   :						List[Any]      							=					[]
							if curr_node is not None:
														__UpperCAmelCase   :						List[Any]      							=					postorder(curr_node.left							) + postorder(curr_node.right							) + [curr_node]
							return node_list
def      lowerCamelCase       (     )		->       None:

							'''simple docstring'''



							__UpperCAmelCase   :						Optional[Any]      							=					(8, 3, 6, 1, 1_0, 1_4, 1_3, 4, 7)
							__UpperCAmelCase   :						Tuple      							=					BinarySearchTree()
							for i in testlist:
														t.insert(_UpperCamelCase							)

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

							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(_UpperCamelCase							)
														print(_UpperCamelCase							)


if __name__ == "__main__":
							import doctest

							doctest.testmod(verbose=True)




"""simple docstring"""






def      lowerCamelCase       (     _UpperCamelCase		:      float       ,			_UpperCamelCase		:      float       ,			_UpperCamelCase		:      int							)		->       float:

							'''simple docstring'''



							if principal <= 0:
														raise Exception("""Principal borrowed must be > 0"""							)
							if rate_per_annum < 0:
														raise Exception("""Rate of interest must be >= 0"""							)
							if years_to_repay <= 0 or not isinstance(_UpperCamelCase       ,			_UpperCamelCase							):
														raise Exception("""Years to repay must be an integer > 0"""							)

							# Yearly rate is divided by 12 to get monthly rate
							__UpperCAmelCase   :						List[Any]      							=					rate_per_annum / 1_2

							# Years to repay is multiplied by 12 to get number of payments as payment is monthly
							__UpperCAmelCase   :						Optional[int]      							=					years_to_repay * 1_2

							return (
							    principal
							    * rate_per_month
							    * (1 + rate_per_month) ** number_of_payments
							    / ((1 + rate_per_month) ** number_of_payments - 1)
							)


if __name__ == "__main__":
							import doctest

							doctest.testmod()
