

from __future__ import annotations

import unittest
from collections.abc import Iterator
class     SCREAMING_SNAKE_CASE__     :





       '''simple docstring'''




       def __init__(						self       :						List[Any]    ,		lowerCAmelCase__       :						int    ,		lowerCAmelCase__       :						Node | None							)			->    None:
             snake_case__					=   label
             snake_case__					=   parent
             snake_case__					=   None
             snake_case__					=   None



class     SCREAMING_SNAKE_CASE__     :





       '''simple docstring'''




       def __init__(						self       :						Union[str, Any]							)			->    None:
             snake_case__					=   None

       def UpperCAmelCase_						(						self       :						List[str]							)			->    None:
             snake_case__					=   None

       def UpperCAmelCase_						(						self       :						str							)			->    bool:
             return self.root is None

       def UpperCAmelCase_						(						self       :						int    ,		lowerCAmelCase__       :						int							)			->    None:
             snake_case__					=   self._put(self.root    ,		lowerCAmelCase__							)

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

             return node

       def UpperCAmelCase_						(						self       :						Tuple    ,		lowerCAmelCase__       :						int							)			->    Node:
             return self._search(self.root    ,		lowerCAmelCase__							)

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

             return node

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

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

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

             return lowest_node

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

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

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

             return node.label

       def UpperCAmelCase_						(						self       :						Union[str, Any]							)			->    int:
             if self.root is None:
                   raise Exception("""Binary search tree is empty"""							)

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

             return node.label

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

       def UpperCAmelCase_						(						self       :						Optional[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       :						List[str]							)			->    Iterator[Node]:
             return self._preorder_traversal(self.root							)

       def UpperCAmelCase_						(						self       :						Dict    ,		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     SCREAMING_SNAKE_CASE__     (						unittest.TestCase		):





       '''simple docstring'''




       @staticmethod
       def UpperCAmelCase_						(						)			->    BinarySearchTree:
             snake_case__					=   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							)

             return t

       def UpperCAmelCase_						(						self       :						Optional[Any]							)			->    None:
             snake_case__					=   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(10							)
             assert t.root.right is not None
             assert t.root.right.parent == t.root
             assert t.root.right.label == 10

             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       :						Optional[int]							)			->    None:
             snake_case__					=   self._get_binary_search_tree()

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

             snake_case__					=   t.search(13							)
             assert node.label == 13

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

       def UpperCAmelCase_						(						self       :						Dict							)			->    None:
             snake_case__					=   self._get_binary_search_tree()

             t.remove(13							)
             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       :						Optional[Any]							)			->    None:
             snake_case__					=   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       :						Dict							)			->    None:
             snake_case__					=   self._get_binary_search_tree()
             t.empty()
             assert t.root is None

       def UpperCAmelCase_						(						self       :						List[Any]							)			->    None:
             snake_case__					=   self._get_binary_search_tree()
             assert not t.is_empty()

             t.empty()
             assert t.is_empty()

       def UpperCAmelCase_						(						self       :						Optional[int]							)			->    None:
             snake_case__					=   self._get_binary_search_tree()

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

       def UpperCAmelCase_						(						self       :						List[Any]							)			->    None:
             snake_case__					=   self._get_binary_search_tree()

             assert t.get_max_label() == 14

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

       def UpperCAmelCase_						(						self       :						Union[str, Any]							)			->    None:
             snake_case__					=   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       :						Optional[Any]							)			->    None:
             snake_case__					=   self._get_binary_search_tree()

             snake_case__					=   [i.label for i in t.inorder_traversal()]
             assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 10, 13, 14]

       def UpperCAmelCase_						(						self       :						int							)			->    None:
             snake_case__					=   self._get_binary_search_tree()

             snake_case__					=   [i.label for i in t.preorder_traversal()]
             assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 10, 14, 13]





def 			_lowercase    (      ):
      snake_case__					=   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(
          """
            8
           / \\
          3   10
         / \\    \\
        1   6    14
           / \\   /
          4   7 13
           \\
            5
        """ )

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

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

      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(
          """
          4
         / \\
        1   7
             \\
              5
        """ )
      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
      snake_case__					=   [i.label for i in t.inorder_traversal()]
      print("""Inorder traversal after delete:"""   ,       __UpperCamelCase )

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

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


if __name__ == "__main__":
       binary_search_tree_example()









lowerCAmelCase						:   Optional[Any]										=    1000





def 			_lowercase    (      __UpperCamelCase     :		float ):
      return x * x





def 			_lowercase    (      __UpperCamelCase     :		int   ,       __UpperCamelCase     :		float   ,       __UpperCamelCase     :		float   ,       __UpperCamelCase     :		int = 4 ):
      assert callable(
          __UpperCamelCase ), F'''the function(object) passed should be callable your input : {function}'''
      assert isinstance(__UpperCamelCase   ,       (float, int) ), F'''a should be float or integer your input : {a}'''
      assert isinstance(function(__UpperCamelCase )   ,       (float, int) ), (
          "the function should return integer or float return type of your function, "
          F'''{type(__UpperCamelCase )}'''
      )
      assert isinstance(__UpperCamelCase   ,       (float, int) ), F'''b should be float or integer your input : {b}'''
      assert (
          isinstance(__UpperCamelCase   ,       __UpperCamelCase ) and precision > 0
      ), F'''precision should be positive integer your input : {precision}'''

      # just applying the formula of simpson for approximate integration written in
      # mentioned article in first comment of this file and above this function

      snake_case__					=   (b - a) / N_STEPS
      snake_case__					=   function(__UpperCamelCase ) + function(__UpperCamelCase )

      for i in range(1   ,       __UpperCamelCase ):
            snake_case__					=   a + h * i
            result += function(__UpperCamelCase ) * (4 if i % 2 else 2)

      result *= h / 3
      return round(__UpperCamelCase   ,       __UpperCamelCase )


if __name__ == "__main__":
       import doctest

       doctest.testmod()






