

from __future__ import annotations

import unittest
from collections.abc import Iterator





class    __UpperCAmelCase	:



   def __init__(				self				:	Optional[Any],						__A				:	int,						__A				:	Node | None		):
     UpperCAmelCase			:				Optional[int]										=					label
     UpperCAmelCase			:				Union[str, Any]										=					parent
     UpperCAmelCase			:				Node | None										=					None
     UpperCAmelCase			:				Node | None										=					None






class    __UpperCAmelCase	:



   def __init__(				self				:	Dict		):
     UpperCAmelCase			:				Node | None										=					None



   def 			__magic_name__       (				self				:	Any		):
     UpperCAmelCase			:				int										=					None



   def 			__magic_name__       (				self				:	Any		):
     return self.root is None



   def 			__magic_name__       (				self				:	Optional[Any],						__A				:	int		):
     UpperCAmelCase			:				List[Any]										=					self._put(self.root,						__A		)



   def 			__magic_name__       (				self				:	List[str],						__A				:	Node | None,						__A				:	int,						__A				:	Node | None = None		):
     if node is None:
       UpperCAmelCase			:				str										=					Node(__A,						__A		)
     else:
       if label < node.label:
         UpperCAmelCase			:				Dict										=					self._put(node.left,						__A,						__A		)
       elif label > node.label:
         UpperCAmelCase			:				List[Any]										=					self._put(node.right,						__A,						__A		)
       else:
         UpperCAmelCase			:				str										=					F'''Node with label {label} already exists'''
         raise Exception(__A		)

     return node



   def 			__magic_name__       (				self				:	List[str],						__A				:	int		):
     return self._search(self.root,						__A		)



   def 			__magic_name__       (				self				:	str,						__A				:	Node | None,						__A				:	int		):
     if node is None:
       UpperCAmelCase			:				Optional[Any]										=					F'''Node with label {label} does not exist'''
       raise Exception(__A		)
     else:
       if label < node.label:
         UpperCAmelCase			:				List[str]										=					self._search(node.left,						__A		)
       elif label > node.label:
         UpperCAmelCase			:				str										=					self._search(node.right,						__A		)

     return node



   def 			__magic_name__       (				self				:	Dict,						__A				:	int		):
     UpperCAmelCase			:				Any										=					self.search(__A		)
     if node.right and node.left:
       UpperCAmelCase			:				int										=					self._get_lowest_node(node.right		)
       UpperCAmelCase			:				Optional[int]										=					node.left
       UpperCAmelCase			:				int										=					node.right
       UpperCAmelCase			:				Optional[int]										=					lowest_node
       if node.right:
         UpperCAmelCase			:				Union[str, Any]										=					lowest_node
       self._reassign_nodes(__A,						__A		)
     elif not node.right and node.left:
       self._reassign_nodes(__A,						node.left		)
     elif node.right and not node.left:
       self._reassign_nodes(__A,						node.right		)
     else:
       self._reassign_nodes(__A,						__A		)



   def 			__magic_name__       (				self				:	Tuple,						__A				:	Node,						__A				:	Node | None		):
     if new_children:
       UpperCAmelCase			:				Optional[Any]										=					node.parent

     if node.parent:
       if node.parent.right == node:
         UpperCAmelCase			:				List[Any]										=					new_children
       else:
         UpperCAmelCase			:				Optional[Any]										=					new_children
     else:
       UpperCAmelCase			:				Union[str, Any]										=					new_children



   def 			__magic_name__       (				self				:	List[Any],						__A				:	Node		):
     if node.left:
       UpperCAmelCase			:				List[Any]										=					self._get_lowest_node(node.left		)
     else:
       UpperCAmelCase			:				Optional[Any]										=					node
       self._reassign_nodes(__A,						node.right		)

     return lowest_node



   def 			__magic_name__       (				self				:	Tuple,						__A				:	int		):
     try:
       self.search(__A		)
       return True
     except Exception:
       return False



   def 			__magic_name__       (				self				:	Union[str, Any]		):
     if self.root is None:
       raise Exception('''Binary search tree is empty'''		)

     UpperCAmelCase			:				Any										=					self.root
     while node.right is not None:
       UpperCAmelCase			:				Union[str, Any]										=					node.right

     return node.label



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

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

     return node.label



   def 			__magic_name__       (				self				:	Any		):
     return self._inorder_traversal(self.root		)



   def 			__magic_name__       (				self				:	str,						__A				:	Node | None		):
     if node is not None:
       yield from self._inorder_traversal(node.left		)
       yield node
       yield from self._inorder_traversal(node.right		)



   def 			__magic_name__       (				self				:	List[Any]		):
     return self._preorder_traversal(self.root		)





   def 			__magic_name__       (				self				:	str,						__A				:	Node | None		):
     if node is not None:
       yield node
       yield from self._preorder_traversal(node.left		)
       yield from self._preorder_traversal(node.right		)






class    __UpperCAmelCase	(			unittest.TestCase		):



   @staticmethod
   def 			__magic_name__       (				):
     UpperCAmelCase			:				Optional[Any]										=					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 			__magic_name__       (				self				:	Union[str, Any]		):
     UpperCAmelCase			:				Tuple										=					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(__A		):  # noqa: B017
       t.put(1		)



   def 			__magic_name__       (				self				:	List[str]		):
     UpperCAmelCase			:				str										=					self._get_binary_search_tree()

     UpperCAmelCase			:				Optional[Any]										=					t.search(6		)
     assert node.label == 6

     UpperCAmelCase			:				Optional[Any]										=					t.search(1_3		)
     assert node.label == 1_3

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



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



   def 			__magic_name__       (				self				:	str		):
     UpperCAmelCase			:				Any										=					self._get_binary_search_tree()
     assert not t.is_empty()

     t.empty()
     assert t.is_empty()



   def 			__magic_name__       (				self				:	Optional[int]		):
     UpperCAmelCase			:				str										=					self._get_binary_search_tree()

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



   def 			__magic_name__       (				self				:	str		):
     UpperCAmelCase			:				int										=					self._get_binary_search_tree()

     assert t.get_max_label() == 1_4

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



   def 			__magic_name__       (				self				:	Union[str, Any]		):
     UpperCAmelCase			:				Any										=					self._get_binary_search_tree()

     assert t.get_min_label() == 1

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



   def 			__magic_name__       (				self				:	Optional[int]		):
     UpperCAmelCase			:				Any										=					self._get_binary_search_tree()

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

     UpperCAmelCase			:				int										=					[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      a__	(						)    ->		None:
  UpperCAmelCase			:				Tuple										=					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
  UpperCAmelCase			:				Any										=					[i.label for i in t.inorder_traversal()]
  print('''Inorder traversal:'''							,					UpperCAmelCase     )

  # Prints all the elements of the list in preorder traversal
  UpperCAmelCase			:				Optional[int]										=					[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
  UpperCAmelCase			:				List[Any]										=					[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
  UpperCAmelCase			:				Dict										=					[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()








import timeit





class    __UpperCAmelCase	:



   def __init__(				self				:	Dict,						__A				:	Union[str, Any]		):
     if isinstance(__A,						__A		):  # Initializes a matrix identical to the one provided.
       UpperCAmelCase			:				str										=					arg
       UpperCAmelCase			:				Optional[Any]										=					len(__A		)
     else:  # Initializes a square matrix of the given size and set values to zero.
       UpperCAmelCase			:				List[str]										=					arg
       UpperCAmelCase			:				List[Any]										=					[[0 for _ in range(self.n		)] for _ in range(self.n		)]





   def __mul__(				self				:	Dict,						__A				:	List[Any]		):
     UpperCAmelCase			:				Dict										=					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      a__	(						UpperCAmelCase				:     List[str]							,					UpperCAmelCase				:     List[Any]     )    ->		str:
  UpperCAmelCase			:				Tuple										=					Matrix([[1, 0], [0, 1]]     )
  while b > 0:
    if b & 1:
      matrix *= a
    a *= a
    b >>= 1
  return matrix

def      a__	(						UpperCAmelCase				:     Any							,					UpperCAmelCase				:     Dict							,					UpperCAmelCase				:     Dict     )    ->		str:
  # Trivial Cases
  if n == 1:
    return fa
  elif n == 2:
    return fa
  UpperCAmelCase			:				List[str]										=					Matrix([[1, 1], [1, 0]]     )
  UpperCAmelCase			:				Union[str, Any]										=					modular_exponentiation(UpperCAmelCase							,					n - 2     )
  return fa * matrix.t[0][0] + fa * matrix.t[0][1]

def      a__	(						UpperCAmelCase				:     Any							,					UpperCAmelCase				:     int							,					UpperCAmelCase				:     List[Any]     )    ->		Optional[Any]:
  # Trivial Cases
  if n == 1:
    return fa
  elif n == 2:
    return fa

  UpperCAmelCase			:				str										=					fa
  UpperCAmelCase			:				List[str]										=					fa
  n -= 2

  while n > 0:
    UpperCAmelCase					,		UpperCAmelCase			:				str										=					fn_a + fn_a, fn_a
    n -= 1

  return fn_a

def      a__	(						)    ->		Any:
  UpperCAmelCase			:				int										=					'''
from random import randint
from __main__ import fibonacci_with_matrix_exponentiation
'''
  UpperCAmelCase			:				Dict										=					'''fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)'''
  UpperCAmelCase			:				Tuple										=					timeit.timeit(setup=UpperCAmelCase							,					stmt=UpperCAmelCase							,					number=100     )
  print('''With matrix exponentiation the average execution time is '''							,					exec_time / 100     )
  return exec_time

def      a__	(						)    ->		int:
  UpperCAmelCase			:				str										=					'''
from random import randint
from __main__ import simple_fibonacci
'''
  UpperCAmelCase			:				List[str]										=					'''simple_fibonacci(randint(1,70000), 1, 1)'''
  UpperCAmelCase			:				List[str]										=					timeit.timeit(setup=UpperCAmelCase							,					stmt=UpperCAmelCase							,					number=100     )
  print(
      '''Without matrix exponentiation the average execution time is '''							,					exec_time / 100     )
  return exec_time

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


if __name__ == "__main__":
     main()





