





'''simple docstring'''

from __future__ import annotations

import unittest
from collections.abc import Iterator


class  a_					:

      '''simple docstring'''


      def __init__(		self			,		A			,		A	)		->       None:
          _SCREAMING_SNAKE_CASE     =      label
          _SCREAMING_SNAKE_CASE     =      parent
          _SCREAMING_SNAKE_CASE     =      None
          _SCREAMING_SNAKE_CASE     =      None




class  a_					:

      '''simple docstring'''


      def __init__(		self	)		->       None:
          _SCREAMING_SNAKE_CASE     =      None


      def       snake_case_(		self	)		->       None:
          _SCREAMING_SNAKE_CASE     =      None


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


      def       snake_case_(		self			,		A	)		->       None:
          _SCREAMING_SNAKE_CASE     =      self._put(self.root			,		SCREAMING_SNAKE_CASE_	)


      def       snake_case_(		self			,		A			,		A			,		A = None	)		->       Node:






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

          return node


      def       snake_case_(		self			,		A	)		->       Node:
          return self._search(self.root			,		SCREAMING_SNAKE_CASE_	)


      def       snake_case_(		self			,		A			,		A	)		->       Node:






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

          return node


      def       snake_case_(		self			,		A	)		->       None:
          _SCREAMING_SNAKE_CASE     =      self.search(SCREAMING_SNAKE_CASE_	)
          if node.right and node.left:
              _SCREAMING_SNAKE_CASE     =      self._get_lowest_node(node.right	)
              _SCREAMING_SNAKE_CASE     =      node.left
              _SCREAMING_SNAKE_CASE     =      node.right
              _SCREAMING_SNAKE_CASE     =      lowest_node
              if node.right:
                  _SCREAMING_SNAKE_CASE     =      lowest_node
              self._reassign_nodes(SCREAMING_SNAKE_CASE_			,		SCREAMING_SNAKE_CASE_	)
          elif not node.right and node.left:
              self._reassign_nodes(SCREAMING_SNAKE_CASE_			,		node.left	)
          elif node.right and not node.left:
              self._reassign_nodes(SCREAMING_SNAKE_CASE_			,		node.right	)
          else:
              self._reassign_nodes(SCREAMING_SNAKE_CASE_			,		SCREAMING_SNAKE_CASE_	)


      def       snake_case_(		self			,		A			,		A	)		->       None:






          if new_children:
              _SCREAMING_SNAKE_CASE     =      node.parent

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


      def       snake_case_(		self			,		A	)		->       Node:






          if node.left:
              _SCREAMING_SNAKE_CASE     =      self._get_lowest_node(node.left	)
          else:
              _SCREAMING_SNAKE_CASE     =      node
              self._reassign_nodes(SCREAMING_SNAKE_CASE_			,		node.right	)

          return lowest_node


      def       snake_case_(		self			,		A	)		->       bool:






          try:
              self.search(SCREAMING_SNAKE_CASE_	)
              return True
          except Exception:
              return False


      def       snake_case_(		self	)		->       int:






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

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

          return node.label


      def       snake_case_(		self	)		->       int:






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

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

          return node.label


      def       snake_case_(		self	)		->       Iterator[Node]:
          return self._inorder_traversal(self.root	)


      def       snake_case_(		self			,		A	)		->       Iterator[Node]:






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


      def       snake_case_(		self	)		->       Iterator[Node]:
          return self._preorder_traversal(self.root	)





      def       snake_case_(		self			,		A	)		->       Iterator[Node]:






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




class  a_					(    unittest.TestCase	):

      '''simple docstring'''


      @staticmethod
      def       snake_case_(		)		->       BinarySearchTree:
          _SCREAMING_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       snake_case_(		self	)		->       None:
          _SCREAMING_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(SCREAMING_SNAKE_CASE_	):  # noqa: B017
              t.put(1	)


      def       snake_case_(		self	)		->       None:
          _SCREAMING_SNAKE_CASE     =      self._get_binary_search_tree()

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

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

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


      def       snake_case_(		self	)		->       None:
          _SCREAMING_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       snake_case_(		self	)		->       None:
          _SCREAMING_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       snake_case_(		self	)		->       None:
          _SCREAMING_SNAKE_CASE     =      self._get_binary_search_tree()
          t.empty()
          assert t.root is None


      def       snake_case_(		self	)		->       None:
          _SCREAMING_SNAKE_CASE     =      self._get_binary_search_tree()
          assert not t.is_empty()

          t.empty()
          assert t.is_empty()


      def       snake_case_(		self	)		->       None:
          _SCREAMING_SNAKE_CASE     =      self._get_binary_search_tree()

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


      def       snake_case_(		self	)		->       None:
          _SCREAMING_SNAKE_CASE     =      self._get_binary_search_tree()

          assert t.get_max_label() == 14

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


      def       snake_case_(		self	)		->       None:
          _SCREAMING_SNAKE_CASE     =      self._get_binary_search_tree()

          assert t.get_min_label() == 1

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


      def       snake_case_(		self	)		->       None:
          _SCREAMING_SNAKE_CASE     =      self._get_binary_search_tree()

          _SCREAMING_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       snake_case_(		self	)		->       None:
          _SCREAMING_SNAKE_CASE     =      self._get_binary_search_tree()

          _SCREAMING_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 lowerCamelCase						(					)						->None:
    _SCREAMING_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
    _SCREAMING_SNAKE_CASE     =      [i.label for i in t.inorder_traversal()]
    print("""Inorder traversal:""" ,	__lowerCamelCase   )

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

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

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

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


if __name__ == "__main__":
      binary_search_tree_example()










'''simple docstring'''

import timeit


class  a_					:

    '''simple docstring'''


    def __init__(		self			,		A	)		->       Optional[int]:
        if isinstance(A			,		A	):  # Initializes a matrix identical to the one provided.
            _SCREAMING_SNAKE_CASE     =      arg
            _SCREAMING_SNAKE_CASE     =      len(A	)
        else:  # Initializes a square matrix of the given size and set values to zero.
            _SCREAMING_SNAKE_CASE     =      arg
            _SCREAMING_SNAKE_CASE     =      [[0 for _ in range(self.n	)] for _ in range(self.n	)]





    def __mul__(		self			,		A	)		->       Optional[int]:
        _SCREAMING_SNAKE_CASE     =      Matrix(self.n	)
        for i in range(self.n	):
            for j in range(self.n	):
                for k in range(self.n	):
                    matrix.t[i][j] += self.t[i][k] * b.t[k][j]
        return matrix





def lowerCamelCase						(					__lowerCamelCase			:   List[str] ,	__lowerCamelCase			:   Optional[int]   )						->int:
    _SCREAMING_SNAKE_CASE     =      Matrix([[1, 0], [0, 1]]   )
    while b > 0:
        if b & 1:
            matrix *= a
        a *= a
        b >>= 1
    return matrix





def lowerCamelCase						(					__lowerCamelCase			:   List[Any] ,	__lowerCamelCase			:   int ,	__lowerCamelCase			:   Tuple   )						->Dict:
    # Trivial Cases
    if n == 1:
        return fa
    elif n == 2:
        return fa
    _SCREAMING_SNAKE_CASE     =      Matrix([[1, 1], [1, 0]]   )
    _SCREAMING_SNAKE_CASE     =      modular_exponentiation(__lowerCamelCase ,	n - 2   )
    return fa * matrix.t[0][0] + fa * matrix.t[0][1]





def lowerCamelCase						(					__lowerCamelCase			:   str ,	__lowerCamelCase			:   List[Any] ,	__lowerCamelCase			:   Tuple   )						->str:
    # Trivial Cases
    if n == 1:
        return fa
    elif n == 2:
        return fa

    _SCREAMING_SNAKE_CASE     =      fa
    _SCREAMING_SNAKE_CASE     =      fa
    n -= 2

    while n > 0:
        _SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE     =      fn_a + fn_a, fn_a
        n -= 1

    return fn_a





def lowerCamelCase						(					)						->str:
    _SCREAMING_SNAKE_CASE     =      """
from random import randint
from __main__ import fibonacci_with_matrix_exponentiation
"""
    _SCREAMING_SNAKE_CASE     =      """fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"""
    _SCREAMING_SNAKE_CASE     =      timeit.timeit(setup=__lowerCamelCase ,	stmt=__lowerCamelCase ,	number=100   )
    print("""With matrix exponentiation the average execution time is """ ,	exec_time / 100   )
    return exec_time





def lowerCamelCase						(					)						->int:
    _SCREAMING_SNAKE_CASE     =      """
from random import randint
from __main__ import simple_fibonacci
"""
    _SCREAMING_SNAKE_CASE     =      """simple_fibonacci(randint(1,70000), 1, 1)"""
    _SCREAMING_SNAKE_CASE     =      timeit.timeit(setup=__lowerCamelCase ,	stmt=__lowerCamelCase ,	number=100   )
    print(
        """Without matrix exponentiation the average execution time is """ ,	exec_time / 100   )
    return exec_time





def lowerCamelCase						(					)						->List[str]:
    matrix_exponentiation_time()
    simple_fibonacci_time()


if __name__ == "__main__":
      main()



