

from __future__ import annotations

import unittest
from collections.abc import Iterator






class     __magic_name__     :


 def __init__(    self		:			int      ,    lowerCAmelCase__		:			int      ,    lowerCAmelCase__		:			Node | None     )     ->   None:
   UpperCAmelCase          =	label
   UpperCAmelCase          =	parent
   UpperCAmelCase          =	None
   UpperCAmelCase          =	None






class     __magic_name__     :


 def __init__(    self		:			Optional[int]     )     ->   None:
   UpperCAmelCase          =	None


 def _UpperCamelCase						(    self		:			Dict     )     ->   None:
   UpperCAmelCase          =	None


 def _UpperCamelCase						(    self		:			Optional[Any]     )     ->   bool:
   return self.root is None


 def _UpperCamelCase						(    self		:			Optional[int]      ,    lowerCAmelCase__		:			int     )     ->   None:
   UpperCAmelCase          =	self._put(self.root      ,    lowerCAmelCase__     )


 def _UpperCamelCase						(    self		:			Optional[Any]      ,    lowerCAmelCase__		:			Node | None      ,    lowerCAmelCase__		:			int      ,    lowerCAmelCase__		:			Node | None = None     )     ->   Node:
   if node is None:
     UpperCAmelCase          =	Node(lowerCAmelCase__      ,    lowerCAmelCase__     )
   else:
     if label < node.label:
       UpperCAmelCase          =	self._put(node.left      ,    lowerCAmelCase__      ,    lowerCAmelCase__     )
     elif label > node.label:
       UpperCAmelCase          =	self._put(node.right      ,    lowerCAmelCase__      ,    lowerCAmelCase__     )
     else:
       UpperCAmelCase          =	f"Node with label {label} already exists"
       raise Exception(lowerCAmelCase__     )

   return node


 def _UpperCamelCase						(    self		:			List[str]      ,    lowerCAmelCase__		:			int     )     ->   Node:
   return self._search(self.root      ,    lowerCAmelCase__     )


 def _UpperCamelCase						(    self		:			List[Any]      ,    lowerCAmelCase__		:			Node | None      ,    lowerCAmelCase__		:			int     )     ->   Node:
   if node is None:
     UpperCAmelCase          =	f"Node with label {label} does not exist"
     raise Exception(lowerCAmelCase__     )
   else:
     if label < node.label:
       UpperCAmelCase          =	self._search(node.left      ,    lowerCAmelCase__     )
     elif label > node.label:
       UpperCAmelCase          =	self._search(node.right      ,    lowerCAmelCase__     )

   return node


 def _UpperCamelCase						(    self		:			List[str]      ,    lowerCAmelCase__		:			int     )     ->   None:
   UpperCAmelCase          =	self.search(lowerCAmelCase__     )
   if node.right and node.left:
     UpperCAmelCase          =	self._get_lowest_node(node.right     )
     UpperCAmelCase          =	node.left
     UpperCAmelCase          =	node.right
     UpperCAmelCase          =	lowest_node
     if node.right:
       UpperCAmelCase          =	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 _UpperCamelCase						(    self		:			Tuple      ,    lowerCAmelCase__		:			Node      ,    lowerCAmelCase__		:			Node | None     )     ->   None:
   if new_children:
     UpperCAmelCase          =	node.parent

   if node.parent:
     if node.parent.right == node:
       UpperCAmelCase          =	new_children
     else:
       UpperCAmelCase          =	new_children
   else:
     UpperCAmelCase          =	new_children


 def _UpperCamelCase						(    self		:			int      ,    lowerCAmelCase__		:			Node     )     ->   Node:
   if node.left:
     UpperCAmelCase          =	self._get_lowest_node(node.left     )
   else:
     UpperCAmelCase          =	node
     self._reassign_nodes(lowerCAmelCase__      ,    node.right     )

   return lowest_node


 def _UpperCamelCase						(    self		:			str      ,    lowerCAmelCase__		:			int     )     ->   bool:
   try:
     self.search(lowerCAmelCase__     )
     return True
   except Exception:
     return False


 def _UpperCamelCase						(    self		:			Optional[Any]     )     ->   int:
   if self.root is None:
     raise Exception("Binary search tree is empty"     )

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

   return node.label


 def _UpperCamelCase						(    self		:			Tuple     )     ->   int:
   if self.root is None:
     raise Exception("Binary search tree is empty"     )

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

   return node.label


 def _UpperCamelCase						(    self		:			Optional[Any]     )     ->   Iterator[Node]:
   return self._inorder_traversal(self.root     )


 def _UpperCamelCase						(    self		:			int      ,    lowerCAmelCase__		:			Node | None     )     ->   Iterator[Node]:
   if node is not None:
     yield from self._inorder_traversal(node.left     )
     yield node
     yield from self._inorder_traversal(node.right     )


 def _UpperCamelCase						(    self		:			Union[str, Any]     )     ->   Iterator[Node]:
   return self._preorder_traversal(self.root     )


 def _UpperCamelCase						(    self		:			List[str]      ,    lowerCAmelCase__		:			Node | None     )     ->   Iterator[Node]:
   if node is not None:
     yield node
     yield from self._preorder_traversal(node.left     )
     yield from self._preorder_traversal(node.right     )






class     __magic_name__     (							unittest.TestCase     ):


 @staticmethod
 def _UpperCamelCase						(    )     ->   BinarySearchTree:
   UpperCAmelCase          =	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 _UpperCamelCase						(    self		:			List[Any]     )     ->   None:
   UpperCAmelCase          =	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 _UpperCamelCase						(    self		:			Dict     )     ->   None:
   UpperCAmelCase          =	self._get_binary_search_tree()

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

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

   with self.assertRaises(lowerCAmelCase__     ):  # noqa: B017
     t.search(2     )


 def _UpperCamelCase						(    self		:			Optional[int]     )     ->   None:
   UpperCAmelCase          =	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 _UpperCamelCase						(    self		:			List[Any]     )     ->   None:
   UpperCAmelCase          =	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 _UpperCamelCase						(    self		:			List[str]     )     ->   None:
   UpperCAmelCase          =	self._get_binary_search_tree()
   t.empty()
   assert t.root is None


 def _UpperCamelCase						(    self		:			Union[str, Any]     )     ->   None:
   UpperCAmelCase          =	self._get_binary_search_tree()
   assert not t.is_empty()

   t.empty()
   assert t.is_empty()


 def _UpperCamelCase						(    self		:			Any     )     ->   None:
   UpperCAmelCase          =	self._get_binary_search_tree()

   assert t.exists(6     )
   assert not t.exists(-1     )


 def _UpperCamelCase						(    self		:			Union[str, Any]     )     ->   None:
   UpperCAmelCase          =	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 _UpperCamelCase						(    self		:			List[str]     )     ->   None:
   UpperCAmelCase          =	self._get_binary_search_tree()

   assert t.get_min_label() == 1

   t.empty()
   with self.assertRaises(lowerCAmelCase__     ):  # noqa: B017
     t.get_min_label()


 def _UpperCamelCase						(    self		:			List[Any]     )     ->   None:
   UpperCAmelCase          =	self._get_binary_search_tree()

   UpperCAmelCase          =	[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 _UpperCamelCase						(    self		:			Any     )     ->   None:
   UpperCAmelCase          =	self._get_binary_search_tree()

   UpperCAmelCase          =	[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   _lowerCAmelCase(						):
  UpperCAmelCase          =	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
  UpperCAmelCase          =	[i.label for i in t.inorder_traversal()]
  print("Inorder traversal:" ,							__A      )

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

  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
  UpperCAmelCase          =	[i.label for i in t.inorder_traversal()]
  print("Inorder traversal after delete:" ,							__A      )

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

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


if __name__ == "__main__":
      binary_search_tree_example()






def   _lowerCAmelCase(						):

  for a in range(300      ):
    for b in range(a + 1 ,							400      ):
      for c in range(b + 1 ,							500      ):
        if (a + b + c) == 1000 and (a**2) + (b**2) == (c**2):
          return a * b * c

  return -1
def   _lowerCAmelCase(						):

  for a in range(300      ):
    for b in range(400      ):
      UpperCAmelCase          =	1000 - a - b
      if a < b < c and (a**2) + (b**2) == (c**2):
        return a * b * c

  return -1
def   _lowerCAmelCase(						):
  import timeit

  print(
      timeit.timeit("solution()" ,							setup="from __main__ import solution" ,							number=1000      )      )
  print(
      timeit.timeit(
          "solution_fast()" ,							setup="from __main__ import solution_fast" ,							number=1000      )      )


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



