




"""simple docstring"""
from collections.abc import Iterable
from typing import Any



class   lowerCAmelCase_    :



				"""simple docstring"""

				def __init__(				self		,    lowerCAmelCase = None    ):






										"""simple docstring"""

										snake_case								=			value
										snake_case								=			None  # Added in order to delete a node easier
										snake_case								=			None
										snake_case								=			None

				def __repr__(				self    ):






										"""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		,    lowerCAmelCase = None    ):






										"""simple docstring"""

										snake_case								=			root

				def __str__(				self    ):






										"""simple docstring"""

										return str(self.root    )

				def 		snake_case (				self		,    lowerCAmelCase		,    lowerCAmelCase    ):






										"""simple docstring"""

										if new_children is not None:  # reset its kids
																snake_case								=			node.parent
										if node.parent is not None:  # reset its parent
																if self.is_right(lowerCAmelCase    ):  # If it is the right children
																						snake_case								=			new_children
																else:
																						snake_case								=			new_children
										else:
																snake_case								=			new_children

				def 		snake_case (				self		,    lowerCAmelCase    ):






										"""simple docstring"""

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

				def 		snake_case (				self    ):






										"""simple docstring"""

										return self.root is None

				def 		snake_case (				self		,    lowerCAmelCase    ):






										"""simple docstring"""

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

				def 		snake_case (				self		,    *lowerCAmelCase    ):






										"""simple docstring"""

										for value in values:
																self.__insert(lowerCAmelCase    )

				def 		snake_case (				self		,    lowerCAmelCase    ):






										"""simple docstring"""

										if self.empty():
																raise IndexError('Warning: Tree is empty! please use another.'    )
										else:
																snake_case								=			self.root
																# use lazy evaluation here to avoid NoneType Attribute error
																while node is not None and node.value is not value:
																						snake_case								=			node.left if value < node.value else node.right
																return node

				def 		snake_case (				self		,    lowerCAmelCase = None    ):






										"""simple docstring"""

										if node is None:
																if self.root is None:
																						return None
																snake_case								=			self.root

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

				def 		snake_case (				self		,    lowerCAmelCase = None    ):






										"""simple docstring"""

										if node is None:
																snake_case								=			self.root
										if self.root is None:
																return None
										if not self.empty():
																snake_case								=			self.root
																while node.left is not None:
																						snake_case								=			node.left
										return node

				def 		snake_case (				self		,    lowerCAmelCase    ):






										"""simple docstring"""

										snake_case								=			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:
																						snake_case								=			self.get_max(
																						    node.left    )  # Gets the max value of the left branch
																						self.remove(tmp_node.value    )  # type: ignore
																						snake_case								=			(
																						    tmp_node.value  # type: ignore
																						)  # Assigns the value to the node to delete and keep tree structure

				def 		snake_case (				self		,    lowerCAmelCase    ):






										"""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		,    lowerCAmelCase=None    ):






										"""simple docstring"""

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

				def 		snake_case (				self		,    lowerCAmelCase		,    lowerCAmelCase    ):






										"""simple docstring"""

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

				def 		snake_case (				self		,    lowerCAmelCase		,    lowerCAmelCase    ):






										"""simple docstring"""

										snake_case								=			[]
										self.inorder(lowerCAmelCase		,    lowerCAmelCase    )  # append all values to list using inorder traversal
										return arr[k - 1]





def    lowerCAmelCase__    (			_UpperCamelCase       :				Node | None					)					->				Any:





						"""simple docstring"""






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





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





						"""simple docstring"""






						snake_case								=			(8, 3, 6, 1, 1_0, 1_4, 1_3, 4, 7)
						snake_case								=			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"""
import math





def    lowerCAmelCase__    (			_UpperCamelCase       :				int					)					->				bool:





						"""simple docstring"""






						return math.sqrt(_UpperCamelCase					) * math.sqrt(_UpperCamelCase					) == num





def    lowerCAmelCase__    (			_UpperCamelCase       :				int					)					->				bool:





						"""simple docstring"""






						snake_case								=			0
						snake_case								=			n
						while left <= right:
												snake_case								=			(left + right) // 2
												if mid**2 == n:
																		return True
												elif mid**2 > n:
																		snake_case								=			mid - 1
												else:
																		snake_case								=			mid + 1
						return False


if __name__ == "__main__":
					import doctest

					doctest.testmod()


