


from __future__ import annotations

import unittest
from collections.abc import Iterator

class      __snake_case				:
					def __init__(						self       :						List[str]	,      _lowerCAmelCase       :						int	,      _lowerCAmelCase       :						Node | None  )							->					None:



											'''simple docstring'''





											__magic_name__					=      label
											__magic_name__					=      parent
											__magic_name__					=      None
											__magic_name__					=      None







class      __snake_case				:
					def __init__(						self       :						Tuple  )							->					None:



											'''simple docstring'''





											__magic_name__					=      None
					def 	a			(						self       :						int  )							->					None:



											'''simple docstring'''





											__magic_name__					=      None
					def 	a			(						self       :						Optional[int]  )							->					bool:



											'''simple docstring'''





											return self.root is None
					def 	a			(						self       :						List[str]	,      _lowerCAmelCase       :						int  )							->					None:



											'''simple docstring'''





											__magic_name__					=      self._put(self.root	,      _lowerCAmelCase  )
					def 	a			(						self       :						str	,      _lowerCAmelCase       :						Node | None	,      _lowerCAmelCase       :						int	,      _lowerCAmelCase       :						Node | None = None  )							->					Node:



											'''simple docstring'''





											if node is None:
																	__magic_name__					=      Node(_lowerCAmelCase	,      _lowerCAmelCase  )
											else:
																	if label < node.label:
																							__magic_name__					=      self._put(node.left	,      _lowerCAmelCase	,      _lowerCAmelCase  )
																	elif label > node.label:
																							__magic_name__					=      self._put(node.right	,      _lowerCAmelCase	,      _lowerCAmelCase  )
																	else:
																							__magic_name__					=      F'''Node with label {label} already exists'''
																							raise Exception(_lowerCAmelCase  )

											return node
					def 	a			(						self       :						str	,      _lowerCAmelCase       :						int  )							->					Node:



											'''simple docstring'''





											return self._search(self.root	,      _lowerCAmelCase  )
					def 	a			(						self       :						Dict	,      _lowerCAmelCase       :						Node | None	,      _lowerCAmelCase       :						int  )							->					Node:



											'''simple docstring'''





											if node is None:
																	__magic_name__					=      F'''Node with label {label} does not exist'''
																	raise Exception(_lowerCAmelCase  )
											else:
																	if label < node.label:
																							__magic_name__					=      self._search(node.left	,      _lowerCAmelCase  )
																	elif label > node.label:
																							__magic_name__					=      self._search(node.right	,      _lowerCAmelCase  )

											return node
					def 	a			(						self       :						Optional[Any]	,      _lowerCAmelCase       :						int  )							->					None:



											'''simple docstring'''





											__magic_name__					=      self.search(_lowerCAmelCase  )
											if node.right and node.left:
																	__magic_name__					=      self._get_lowest_node(node.right  )
																	__magic_name__					=      node.left
																	__magic_name__					=      node.right
																	__magic_name__					=      lowest_node
																	if node.right:
																							__magic_name__					=      lowest_node
																	self._reassign_nodes(_lowerCAmelCase	,      _lowerCAmelCase  )
											elif not node.right and node.left:
																	self._reassign_nodes(_lowerCAmelCase	,      node.left  )
											elif node.right and not node.left:
																	self._reassign_nodes(_lowerCAmelCase	,      node.right  )
											else:
																	self._reassign_nodes(_lowerCAmelCase	,      _lowerCAmelCase  )
					def 	a			(						self       :						str	,      _lowerCAmelCase       :						Node	,      _lowerCAmelCase       :						Node | None  )							->					None:



											'''simple docstring'''





											if new_children:
																	__magic_name__					=      node.parent

											if node.parent:
																	if node.parent.right == node:
																							__magic_name__					=      new_children
																	else:
																							__magic_name__					=      new_children
											else:
																	__magic_name__					=      new_children
					def 	a			(						self       :						int	,      _lowerCAmelCase       :						Node  )							->					Node:



											'''simple docstring'''





											if node.left:
																	__magic_name__					=      self._get_lowest_node(node.left  )
											else:
																	__magic_name__					=      node
																	self._reassign_nodes(_lowerCAmelCase	,      node.right  )

											return lowest_node
					def 	a			(						self       :						Dict	,      _lowerCAmelCase       :						int  )							->					bool:



											'''simple docstring'''





											try:
																	self.search(_lowerCAmelCase  )
																	return True
											except Exception:
																	return False
					def 	a			(						self       :						Tuple  )							->					int:



											'''simple docstring'''





											if self.root is None:
																	raise Exception('Binary search tree is empty'  )

											__magic_name__					=      self.root
											while node.right is not None:
																	__magic_name__					=      node.right

											return node.label
					def 	a			(						self       :						Union[str, Any]  )							->					int:



											'''simple docstring'''





											if self.root is None:
																	raise Exception('Binary search tree is empty'  )

											__magic_name__					=      self.root
											while node.left is not None:
																	__magic_name__					=      node.left

											return node.label
					def 	a			(						self       :						Tuple  )							->					Iterator[Node]:



											'''simple docstring'''





											return self._inorder_traversal(self.root  )
					def 	a			(						self       :						Dict	,      _lowerCAmelCase       :						Node | None  )							->					Iterator[Node]:



											'''simple docstring'''





											if node is not None:
																	yield from self._inorder_traversal(node.left  )
																	yield node
																	yield from self._inorder_traversal(node.right  )
					def 	a			(						self       :						Union[str, Any]  )							->					Iterator[Node]:



											'''simple docstring'''





											return self._preorder_traversal(self.root  )







					def 	a			(						self       :						List[str]	,      _lowerCAmelCase       :						Node | None  )							->					Iterator[Node]:



											'''simple docstring'''





											if node is not None:
																	yield node
																	yield from self._preorder_traversal(node.left  )
																	yield from self._preorder_traversal(node.right  )







class      __snake_case				(   unittest.TestCase):
					@staticmethod
					def 	a			(						)							->					BinarySearchTree:



											'''simple docstring'''





											__magic_name__					=      BinarySearchTree()
											t.put(8  )
											t.put(3  )
											t.put(6  )
											t.put(1  )
											t.put(1_0  )
											t.put(1_4  )
											t.put(1_3  )
											t.put(4  )
											t.put(7  )
											t.put(5  )

											return t
					def 	a			(						self       :						int  )							->					None:



											'''simple docstring'''





											__magic_name__					=      BinarySearchTree()
											assert t.is_empty()

											t.put(8  )
											assert t.root is not None
											assert t.root.parent is None
											assert t.root.label == 8

											t.put(1_0  )
											assert t.root.right is not None
											assert t.root.right.parent == t.root
											assert t.root.right.label == 1_0

											t.put(3  )
											assert t.root.left is not None
											assert t.root.left.parent == t.root
											assert t.root.left.label == 3

											t.put(6  )
											assert t.root.left.right is not None
											assert t.root.left.right.parent == t.root.left
											assert t.root.left.right.label == 6

											t.put(1  )
											assert t.root.left.left is not None
											assert t.root.left.left.parent == t.root.left
											assert t.root.left.left.label == 1

											with self.assertRaises(_lowerCAmelCase  ):  # noqa: B017
																	t.put(1  )
					def 	a			(						self       :						List[str]  )							->					None:



											'''simple docstring'''





											__magic_name__					=      self._get_binary_search_tree()

											__magic_name__					=      t.search(6  )
											assert node.label == 6

											__magic_name__					=      t.search(1_3  )
											assert node.label == 1_3

											with self.assertRaises(_lowerCAmelCase  ):  # noqa: B017
																	t.search(2  )
					def 	a			(						self       :						Dict  )							->					None:



											'''simple docstring'''





											__magic_name__					=      self._get_binary_search_tree()

											t.remove(1_3  )
											assert t.root is not None
											assert t.root.right is not None
											assert t.root.right.right is not None
											assert t.root.right.right.right is None
											assert t.root.right.right.left is None

											t.remove(7  )
											assert t.root.left is not None
											assert t.root.left.right is not None
											assert t.root.left.right.left is not None
											assert t.root.left.right.right is None
											assert t.root.left.right.left.label == 4

											t.remove(6  )
											assert t.root.left.left is not None
											assert t.root.left.right.right is not None
											assert t.root.left.left.label == 1
											assert t.root.left.right.label == 4
											assert t.root.left.right.right.label == 5
											assert t.root.left.right.left is None
											assert t.root.left.left.parent == t.root.left
											assert t.root.left.right.parent == t.root.left

											t.remove(3  )
											assert t.root is not None
											assert t.root.left.label == 4
											assert t.root.left.right.label == 5
											assert t.root.left.left.label == 1
											assert t.root.left.parent == t.root
											assert t.root.left.left.parent == t.root.left
											assert t.root.left.right.parent == t.root.left

											t.remove(4  )
											assert t.root.left is not None
											assert t.root.left.left is not None
											assert t.root.left.label == 5
											assert t.root.left.right is None
											assert t.root.left.left.label == 1
											assert t.root.left.parent == t.root
											assert t.root.left.left.parent == t.root.left
					def 	a			(						self       :						int  )							->					None:



											'''simple docstring'''





											__magic_name__					=      self._get_binary_search_tree()

											t.remove(3  )
											assert t.root is not None
											assert t.root.left is not None
											assert t.root.left.left is not None
											assert t.root.left.right is not None
											assert t.root.left.right.left is not None
											assert t.root.left.right.right is not None
											assert t.root.left.label == 4
											assert t.root.left.right.label == 6
											assert t.root.left.left.label == 1
											assert t.root.left.right.right.label == 7
											assert t.root.left.right.left.label == 5
											assert t.root.left.parent == t.root
											assert t.root.left.right.parent == t.root.left
											assert t.root.left.left.parent == t.root.left
											assert t.root.left.right.left.parent == t.root.left.right
					def 	a			(						self       :						Dict  )							->					None:



											'''simple docstring'''





											__magic_name__					=      self._get_binary_search_tree()
											t.empty()
											assert t.root is None
					def 	a			(						self       :						List[Any]  )							->					None:



											'''simple docstring'''





											__magic_name__					=      self._get_binary_search_tree()
											assert not t.is_empty()

											t.empty()
											assert t.is_empty()
					def 	a			(						self       :						int  )							->					None:



											'''simple docstring'''





											__magic_name__					=      self._get_binary_search_tree()

											assert t.exists(6  )
											assert not t.exists(-1  )
					def 	a			(						self       :						Tuple  )							->					None:



											'''simple docstring'''





											__magic_name__					=      self._get_binary_search_tree()

											assert t.get_max_label() == 1_4

											t.empty()
											with self.assertRaises(_lowerCAmelCase  ):  # noqa: B017
																	t.get_max_label()
					def 	a			(						self       :						Any  )							->					None:



											'''simple docstring'''





											__magic_name__					=      self._get_binary_search_tree()

											assert t.get_min_label() == 1

											t.empty()
											with self.assertRaises(_lowerCAmelCase  ):  # noqa: B017
																	t.get_min_label()
					def 	a			(						self       :						int  )							->					None:



											'''simple docstring'''





											__magic_name__					=      self._get_binary_search_tree()

											__magic_name__					=      [i.label for i in t.inorder_traversal()]
											assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 1_0, 1_3, 1_4]







					def 	a			(						self       :						int  )							->					None:



											'''simple docstring'''





											__magic_name__					=      self._get_binary_search_tree()

											__magic_name__					=      [i.label for i in t.preorder_traversal()]
											assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 1_0, 1_4, 1_3]







def 				UpperCamelCase_	(					)->   None:




						'''simple docstring'''
						__magic_name__					=      BinarySearchTree()
						t.put(8  )
						t.put(3  )
						t.put(6  )
						t.put(1  )
						t.put(10  )
						t.put(14  )
						t.put(13  )
						t.put(4  )
						t.put(7  )
						t.put(5  )

						print(
						    '\n            8\n           / \\\n          3   10\n         / \\    \\\n        1   6    14\n           / \\   /\n          4   7 13\n           \\\n            5\n        '  )

						print('Label 6 exists:'						,      t.exists(6  )  )
						print('Label 13 exists:'						,      t.exists(13  )  )
						print('Label -1 exists:'						,      t.exists(-1  )  )
						print('Label 12 exists:'						,      t.exists(12  )  )

						# Prints all the elements of the list in inorder traversal
						__magic_name__					=      [i.label for i in t.inorder_traversal()]
						print('Inorder traversal:'						,      __snake_case  )

						# Prints all the elements of the list in preorder traversal
						__magic_name__					=      [i.label for i in t.preorder_traversal()]
						print('Preorder traversal:'						,      __snake_case  )

						print('Max. label:'						,      t.get_max_label()  )
						print('Min. label:'						,      t.get_min_label()  )

						# Delete elements
						print('\nDeleting elements 13, 10, 8, 3, 6, 14'  )
						print(
						    '\n          4\n         / \\\n        1   7\n             \\\n              5\n        '  )
						t.remove(13  )
						t.remove(10  )
						t.remove(8  )
						t.remove(3  )
						t.remove(6  )
						t.remove(14  )

						# Prints all the elements of the list in inorder traversal after delete
						__magic_name__					=      [i.label for i in t.inorder_traversal()]
						print('Inorder traversal after delete:'						,      __snake_case  )

						# Prints all the elements of the list in preorder traversal after delete
						__magic_name__					=      [i.label for i in t.preorder_traversal()]
						print('Preorder traversal after delete:'						,      __snake_case  )

						print('Max. label:'						,      t.get_max_label()  )
						print('Min. label:'						,      t.get_min_label()  )


if __name__ == "__main__":
					binary_search_tree_example()





from itertools import count
from math import asin, pi, sqrt
def 				UpperCamelCase_	(					__snake_case      :    float  )->   float:




						'''simple docstring'''
						return (
						    (1 - 2 * point) * sqrt(point - point**2  ) + 2 * point + asin(sqrt(1 - point  )  )
						) / 4
def 				UpperCamelCase_	(					__snake_case      :    int  )->   float:




						'''simple docstring'''
						__magic_name__					=      (circles_number + 1 - sqrt(2 * circles_number  )) / (
						    2 * (circles_number**2 + 1)
						)
						__magic_name__					=      circles_number * intersection_y

						__magic_name__					=      intersection_x * intersection_y / 2
						__magic_name__					=      circle_bottom_arc_integral(
						    1 / 2  ) - circle_bottom_arc_integral(__snake_case  )

						return triangle_area + concave_region_area
def 				UpperCamelCase_	(					__snake_case      :    float = 1 / 10_00  )->   int:




						'''simple docstring'''
						__magic_name__					=      (1 - pi / 4) / 4

						for n in count(1  ):
												if concave_triangle_area(__snake_case  ) / l_section_area < fraction:
																		return n

						return -1


if __name__ == "__main__":
					print(f'''{solution() = }''')

