"""simple docstring"""




from collections.abc import Iterable
from typing import Any

class    a_   :




					def __init__(						self    :  List[Any]	,    snake_case__    :  int | None = None  ):
							lowerCAmelCase__   = value
							lowerCAmelCase__   = None  # Added in order to delete a node easier
							lowerCAmelCase__   = None
							lowerCAmelCase__   = None




					def __repr__(						self    :  List[Any]  ):
							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    a_   :




					def __init__(						self    :  Optional[Any]	,    snake_case__    :  Node | None = None  ):
							lowerCAmelCase__   = root




					def __str__(						self    :  Optional[int]  ):
							return str(self.root  )




					def     _SCREAMING_SNAKE_CASE    (						self    :  Optional[int]	,    snake_case__    :  Node	,    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(snake_case__  ):  # If it is the right children
											lowerCAmelCase__   = new_children
									else:
											lowerCAmelCase__   = new_children
							else:
									lowerCAmelCase__   = new_children




					def     _SCREAMING_SNAKE_CASE    (						self    :  Optional[int]	,    snake_case__    :  Node  ):
							if node.parent and node.parent.right:
									return node == node.parent.right
							return False




					def     _SCREAMING_SNAKE_CASE    (						self    :  Any  ):
							return self.root is None




					def     _SCREAMING_SNAKE_CASE    (						self    :  Any	,    snake_case__    :  str  ):
							lowerCAmelCase__   = Node(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     _SCREAMING_SNAKE_CASE    (						self    :  List[str]	,    *snake_case__    :  Dict  ):
							for value in values:
									self.__insert(snake_case__  )




					def     _SCREAMING_SNAKE_CASE    (						self    :  Dict	,    snake_case__    :  str  ):
							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     _SCREAMING_SNAKE_CASE    (						self    :  Dict	,    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     _SCREAMING_SNAKE_CASE    (						self    :  Optional[Any]	,    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     _SCREAMING_SNAKE_CASE    (						self    :  Optional[int]	,    snake_case__    :  int  ):
							lowerCAmelCase__   = self.search(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(snake_case__	,    snake_case__  )
									elif node.left is None:  # Has only right children
											self.__reassign_nodes(snake_case__	,    node.right  )
									elif node.right is None:  # Has only left children
											self.__reassign_nodes(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     _SCREAMING_SNAKE_CASE    (						self    :  Optional[Any]	,    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     _SCREAMING_SNAKE_CASE    (						self    :  Optional[int]	,    snake_case__    :  List[str]=None  ):
							if traversal_function is None:
									return self.preorder_traverse(self.root  )
							else:
									return traversal_function(self.root  )




					def     _SCREAMING_SNAKE_CASE    (						self    :  str	,    snake_case__    :  list	,    snake_case__    :  Node | None  ):
							if node:
									self.inorder(snake_case__	,    node.left  )
									arr.append(node.value  )
									self.inorder(snake_case__	,    node.right  )




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







def 				_UpperCAmelCase		(							lowerCamelCase__  ):





		"""simple docstring"""




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







def 				_UpperCAmelCase		(							):





		"""simple docstring"""




		lowerCAmelCase__   = (8, 3, 6, 1, 10, 14, 13, 4, 7)
		lowerCAmelCase__   = 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"""




from __future__ import annotations

from typing import Any

class    a_   :




					def __init__(						self    :  Union[str, Any]	,    snake_case__    :  int = 6  ):
							lowerCAmelCase__   = None
							lowerCAmelCase__   = None
							self.create_linked_list(snake_case__  )




					def     _SCREAMING_SNAKE_CASE    (						self    :  Tuple	,    snake_case__    :  int  ):
							lowerCAmelCase__   = Node()
							lowerCAmelCase__   = current_node
							lowerCAmelCase__   = current_node
							lowerCAmelCase__   = current_node
							for _ in range(1	,    snake_case__  ):
									lowerCAmelCase__   = Node()
									lowerCAmelCase__   = current_node
									lowerCAmelCase__   = previous_node
									lowerCAmelCase__   = current_node
							lowerCAmelCase__   = self.front
							lowerCAmelCase__   = previous_node




					def     _SCREAMING_SNAKE_CASE    (						self    :  Any  ):
							return (
							    self.front == self.rear
							    and self.front is not None
							    and self.front.data is None
							)




					def     _SCREAMING_SNAKE_CASE    (						self    :  Any  ):
							self.check_can_perform_operation()
							return self.front.data if self.front else None




					def     _SCREAMING_SNAKE_CASE    (						self    :  Dict	,    snake_case__    :  Any  ):
							if self.rear is None:
									return

							self.check_is_full()
							if not self.is_empty():
									lowerCAmelCase__   = self.rear.next
							if self.rear:
									lowerCAmelCase__   = data




					def     _SCREAMING_SNAKE_CASE    (						self    :  Any  ):
							self.check_can_perform_operation()
							if self.rear is None or self.front is None:
									return None
							if self.front == self.rear:
									lowerCAmelCase__   = self.front.data
									lowerCAmelCase__   = None
									return data

							lowerCAmelCase__   = self.front
							lowerCAmelCase__   = old_front.next
							lowerCAmelCase__   = old_front.data
							lowerCAmelCase__   = None
							return data




					def     _SCREAMING_SNAKE_CASE    (						self    :  Union[str, Any]  ):
							if self.is_empty():
									raise Exception("""Empty Queue"""  )




					def     _SCREAMING_SNAKE_CASE    (						self    :  Optional[Any]  ):
							if self.rear and self.rear.next == self.front:
									raise Exception("""Full Queue"""  )

class    a_   :




					def __init__(						self    :  Union[str, Any]  ):
							lowerCAmelCase__   = None
							lowerCAmelCase__   = None
							lowerCAmelCase__   = None


if __name__ == "__main__":
			import doctest

			doctest.testmod()




