






'''simple docstring'''





from collections.abc import Iterable
from typing import Any
class  lowerCAmelCase_       :




							def __init__(   self     :   Tuple ,							SCREAMING_SNAKE_CASE_     :   int | None = None	):
											lowerCAmelCase__      			=						value
											lowerCAmelCase__      			=						None  # Added in order to delete a node easier
											lowerCAmelCase__      			=						None
											lowerCAmelCase__      			=						None




							def __repr__(   self     :   Dict	):
											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_       :




							def __init__(   self     :   Any ,							SCREAMING_SNAKE_CASE_     :   Node | None = None	):
											lowerCAmelCase__      			=						root




							def __str__(   self     :   List[Any]	):
											return str(self.root	)




							def 						__snake_case					(   self     :   int ,							SCREAMING_SNAKE_CASE_     :   Node ,							SCREAMING_SNAKE_CASE_     :   Node | None	):
											if new_children is not None:  # reset its kids
															lowerCAmelCase__      			=						node.parent
											if node.parent is not None:  # reset its parent
															if self.is_right(SCREAMING_SNAKE_CASE_	):  # If it is the right children
																			lowerCAmelCase__      			=						new_children
															else:
																			lowerCAmelCase__      			=						new_children
											else:
															lowerCAmelCase__      			=						new_children




							def 						__snake_case					(   self     :   Union[str, Any] ,							SCREAMING_SNAKE_CASE_     :   Node	):
											if node.parent and node.parent.right:
															return node == node.parent.right
											return False




							def 						__snake_case					(   self     :   Union[str, Any]	):
											return self.root is None




							def 						__snake_case					(   self     :   Dict ,							SCREAMING_SNAKE_CASE_     :   Dict	):
											lowerCAmelCase__      			=						Node(SCREAMING_SNAKE_CASE_	)  # create a new Node
											if self.empty():  # if Tree is empty
															lowerCAmelCase__      			=						new_node  # set its root
											else:  # Tree is not empty
															lowerCAmelCase__      			=						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:
																											lowerCAmelCase__      			=						new_node  # We insert the new node in a leaf
																											break
																							else:
																											lowerCAmelCase__      			=						parent_node.left
																			else:
																							if parent_node.right is None:
																											lowerCAmelCase__      			=						new_node
																											break
																							else:
																											lowerCAmelCase__      			=						parent_node.right
															lowerCAmelCase__      			=						parent_node




							def 						__snake_case					(   self     :   str ,							*SCREAMING_SNAKE_CASE_     :   int	):
											for value in values:
															self.__insert(SCREAMING_SNAKE_CASE_	)




							def 						__snake_case					(   self     :   List[Any] ,							SCREAMING_SNAKE_CASE_     :   Dict	):
											if self.empty():
															raise IndexError('''Warning: Tree is empty! please use another.'''	)
											else:
															lowerCAmelCase__      			=						self.root
															# use lazy evaluation here to avoid NoneType Attribute error
															while node is not None and node.value is not value:
																			lowerCAmelCase__      			=						node.left if value < node.value else node.right
															return node




							def 						__snake_case					(   self     :   str ,							SCREAMING_SNAKE_CASE_     :   Node | None = None	):
											if node is None:
															if self.root is None:
																			return None
															lowerCAmelCase__      			=						self.root

											if not self.empty():
															while node.right is not None:
																			lowerCAmelCase__      			=						node.right
											return node




							def 						__snake_case					(   self     :   List[Any] ,							SCREAMING_SNAKE_CASE_     :   Node | None = None	):
											if node is None:
															lowerCAmelCase__      			=						self.root
											if self.root is None:
															return None
											if not self.empty():
															lowerCAmelCase__      			=						self.root
															while node.left is not None:
																			lowerCAmelCase__      			=						node.left
											return node




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




							def 						__snake_case					(   self     :   Union[str, Any] ,							SCREAMING_SNAKE_CASE_     :   Node | None	):
											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     :   Optional[Any] ,							SCREAMING_SNAKE_CASE_     :   Dict=None	):
											if traversal_function is None:
															return self.preorder_traverse(self.root	)
											else:
															return traversal_function(self.root	)




							def 						__snake_case					(   self     :   int ,							SCREAMING_SNAKE_CASE_     :   list ,							SCREAMING_SNAKE_CASE_     :   Node | None	):
											if node:
															self.inorder(SCREAMING_SNAKE_CASE_ ,							node.left	)
															arr.append(node.value	)
															self.inorder(SCREAMING_SNAKE_CASE_ ,							node.right	)




							def 						__snake_case					(   self     :   List[str] ,							SCREAMING_SNAKE_CASE_     :   int ,							SCREAMING_SNAKE_CASE_     :   Node	):
											lowerCAmelCase__      			=						[]
											self.inorder(SCREAMING_SNAKE_CASE_ ,							SCREAMING_SNAKE_CASE_	)  # append all values to list using inorder traversal
											return arr[k - 1]





def 	lowerCAmelCase_		(lowercase__						:       Node | None       )		->    list[Node]:


				'''simple docstring'''




				lowerCAmelCase__      			=						[]
				if curr_node is not None:
								lowerCAmelCase__      			=						postorder(curr_node.left       ) + postorder(curr_node.right       ) + [curr_node]
				return node_list





def 	lowerCAmelCase_		()		->    None:


				'''simple docstring'''




				lowerCAmelCase__      			=						(8, 3, 6, 1, 10, 14, 13, 4, 7)
				lowerCAmelCase__      			=						BinarySearchTree()
				for i in testlist:
								t.insert(lowercase__       )

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

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


if __name__ == "__main__":
			import doctest

			doctest.testmod(verbose=True)













from __future__ import annotations





def 	lowerCAmelCase_		(lowercase__						:       list[int]       )		->    bool:


				'''simple docstring'''




				return len(set(lowercase__       )       ) == len(lowercase__       )


if __name__ == "__main__":
			import doctest

			doctest.testmod()





