
"""simple docstring"""
from __future__ import annotations
class 			UpperCamelCase      :
     def __init__(     self  ,     snake_case__				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				Optional[int]							    = TypeError(
           "Matrices must be formed from a list of zero or more lists containing at "
           "least one and the same number of values, each of which must be of type "
           "int or float."				)
       if len(snake_case__				) != 0:
         _SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = len(rows[0]				)
         if cols == 0:
           raise error
         for row in rows:
           if len(snake_case__				) != cols:
             raise error
           for value in row:
             if not isinstance(snake_case__  ,     (int, float)				):
               raise error
         _SCREAMING_SNAKE_CASE   :				Tuple							    = rows
       else:
         _SCREAMING_SNAKE_CASE   :				str							    = []
     def 				__SCREAMING_SNAKE_CASE							(     self				):




       """simple docstring"""


       return [[row[i] for row in self.rows] for i in range(len(self.rows[0]				)				)]
     @property
     def 				__SCREAMING_SNAKE_CASE							(     self				):




       """simple docstring"""


       return len(self.rows				)
     @property
     def 				__SCREAMING_SNAKE_CASE							(     self				):




       """simple docstring"""


       return len(self.rows[0]				)
     @property
     def 				__SCREAMING_SNAKE_CASE							(     self				):




       """simple docstring"""


       return (self.num_rows, self.num_columns)
     @property
     def 				__SCREAMING_SNAKE_CASE							(     self				):




       """simple docstring"""


       return self.order[0] == self.order[1]
     def 				__SCREAMING_SNAKE_CASE							(     self				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				int							    = [
           [0 if column_num != row_num else 1 for column_num in range(self.num_rows				)]
           for row_num in range(self.num_rows				)
       ]
       return Matrix(snake_case__				)
     def 				__SCREAMING_SNAKE_CASE							(     self				):




       """simple docstring"""


       if not self.is_square:
         return 0
       if self.order == (0, 0):
         return 1
       if self.order == (1, 1):
         return int(self.rows[0][0]				)
       if self.order == (2, 2):
         return int(
             (self.rows[0][0] * self.rows[1][1])
             - (self.rows[0][1] * self.rows[1][0])				)
       else:
         return sum(
             self.rows[0][column] * self.cofactors().rows[0][column]
             for column in range(self.num_columns				)				)
     def 				__SCREAMING_SNAKE_CASE							(     self				):




       """simple docstring"""


       return bool(self.determinant()				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				List[str]							    = [
           [
               self.rows[other_row][other_column]
               for other_column in range(self.num_columns				)
               if other_column != column
           ]
           for other_row in range(self.num_rows				)
           if other_row != row
       ]
       return Matrix(snake_case__				).determinant()
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__				):




       """simple docstring"""


       if (row + column) % 2 == 0:
         return self.get_minor(snake_case__  ,     snake_case__				)
       return -1 * self.get_minor(snake_case__  ,     snake_case__				)
     def 				__SCREAMING_SNAKE_CASE							(     self				):




       """simple docstring"""


       return Matrix(
           [
               [self.get_minor(snake_case__  ,     snake_case__				) for column in range(self.num_columns				)]
               for row in range(self.num_rows				)
           ]				)
     def 				__SCREAMING_SNAKE_CASE							(     self				):




       """simple docstring"""


       return Matrix(
           [
               [
                   self.minors().rows[row][column]
                   if (row + column) % 2 == 0
                   else self.minors().rows[row][column] * -1
                   for column in range(self.minors().num_columns				)
               ]
               for row in range(self.minors().num_rows				)
           ]				)
     def 				__SCREAMING_SNAKE_CASE							(     self				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				int							    = [
           [self.cofactors().rows[column][row] for column in range(self.num_columns				)]
           for row in range(self.num_rows				)
       ]
       return Matrix(snake_case__				)
     def 				__SCREAMING_SNAKE_CASE							(     self				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				int							    = self.determinant()
       if not determinant:
         raise TypeError("Only matrices with a non-zero determinant have an inverse"				)
       return self.adjugate() * (1 / determinant)
     def __repr__(     self				):




       """simple docstring"""


       return str(self.rows				)
     def __str__(     self				):




       """simple docstring"""


       if self.num_rows == 0:
         return "[]"
       if self.num_rows == 1:
         return "[[" + ". ".join(str(self.rows[0]				)				) + "]]"
       return (
           "["
           + "\n ".join(
               [
                   "[" + ". ".join([str(snake_case__				) for value in row]				) + ".]"
                   for row in self.rows
               ]				)
           + "]"
       )
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__ = None				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				Dict							    = TypeError("Row must be a list containing all ints and/or floats"				)
       if not isinstance(snake_case__  ,     snake_case__				):
         raise type_error
       for value in row:
         if not isinstance(snake_case__  ,     (int, float)				):
           raise type_error
       if len(snake_case__				) != self.num_columns:
         raise ValueError(
             "Row must be equal in length to the other rows in the matrix"				)
       if position is None:
         self.rows.append(snake_case__				)
       else:
         _SCREAMING_SNAKE_CASE   :				Optional[Any]							    = self.rows[0:position] + [row] + self.rows[position:]
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__ = None				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				Optional[Any]							    = TypeError(
           "Column must be a list containing all ints and/or floats"				)
       if not isinstance(snake_case__  ,     snake_case__				):
         raise type_error
       for value in column:
         if not isinstance(snake_case__  ,     (int, float)				):
           raise type_error
       if len(snake_case__				) != self.num_rows:
         raise ValueError(
             "Column must be equal in length to the other columns in the matrix"				)
       if position is None:
         _SCREAMING_SNAKE_CASE   :				Optional[int]							    = [self.rows[i] + [column[i]] for i in range(self.num_rows				)]
       else:
         _SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = [
             self.rows[i][0:position] + [column[i]] + self.rows[i][position:]
             for i in range(self.num_rows				)
         ]
     def __eq__(     self  ,     snake_case__				):




       """simple docstring"""


       if not isinstance(snake_case__  ,     snake_case__				):
         return NotImplemented
       return self.rows == other.rows
     def __ne__(     self  ,     snake_case__				):




       """simple docstring"""


       return not self == other
     def __neg__(     self				):




       """simple docstring"""


       return self * -1
     def __add__(     self  ,     snake_case__				):




       """simple docstring"""


       if self.order != other.order:
         raise ValueError("Addition requires matrices of the same order"				)
       return Matrix(
           [
               [self.rows[i][j] + other.rows[i][j] for j in range(self.num_columns				)]
               for i in range(self.num_rows				)
           ]				)
     def __sub__(     self  ,     snake_case__				):




       """simple docstring"""


       if self.order != other.order:
         raise ValueError("Subtraction requires matrices of the same order"				)
       return Matrix(
           [
               [self.rows[i][j] - other.rows[i][j] for j in range(self.num_columns				)]
               for i in range(self.num_rows				)
           ]				)
     def __mul__(     self  ,     snake_case__				):




       """simple docstring"""


       if isinstance(snake_case__  ,     (int, float)				):
         return Matrix(
             [[int(element * other				) for element in row] for row in self.rows]				)
       elif isinstance(snake_case__  ,     snake_case__				):
         if self.num_columns != other.num_rows:
           raise ValueError(
               "The number of columns in the first matrix must "
               "be equal to the number of rows in the second"				)
         return Matrix(
             [
                 [Matrix.dot_product(snake_case__  ,     snake_case__				) for column in other.columns()]
                 for row in self.rows
             ]				)
       else:
         raise TypeError(
             "A Matrix can only be multiplied by an int, float, or another matrix"				)
     def __pow__(     self  ,     snake_case__				):




       """simple docstring"""


       if not isinstance(snake_case__  ,     snake_case__				):
         raise TypeError("A Matrix can only be raised to the power of an int"				)
       if not self.is_square:
         raise ValueError("Only square matrices can be raised to a power"				)
       if other == 0:
         return self.identity()
       if other < 0:
         if self.is_invertable():
           return self.inverse() ** (-other)
         raise ValueError(
             "Only invertable matrices can be raised to a negative power"				)
       _SCREAMING_SNAKE_CASE   :				Tuple							    = self
       for _ in range(other - 1				):
         result *= self
       return result




     @classmethod
     def 				__SCREAMING_SNAKE_CASE							(     cls  ,     snake_case__  ,     snake_case__				):




       """simple docstring"""


       return sum(row[i] * column[i] for i in range(len(snake_case__				)				)				)


if __name__ == "__main__":
      import doctest

      doctest.testmod()





"""simple docstring"""
from collections.abc import Iterable
from typing import Any
class 			UpperCamelCase      :
     def __init__(     self  ,     snake_case__ = None				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				List[str]							    = value
       _SCREAMING_SNAKE_CASE   :				Node | None							    = None  # Added in order to delete a node easier
       _SCREAMING_SNAKE_CASE   :				Node | None							    = None
       _SCREAMING_SNAKE_CASE   :				Node | None							    = None




     def __repr__(     self				):




       """simple docstring"""


       from pprint import pformat

       if self.left is None and self.right is None:
         return str(self.value				)
       return pformat({F'''{self.value}''': (self.left, self.right)}  ,     indent=1				)
class 			UpperCamelCase      :
     def __init__(     self  ,     snake_case__ = None				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				List[str]							    = root
     def __str__(     self				):




       """simple docstring"""


       return str(self.root				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__				):




       """simple docstring"""


       if new_children is not None:  # reset its kids
         _SCREAMING_SNAKE_CASE   :				Dict							    = node.parent
       if node.parent is not None:  # reset its parent
         if self.is_right(snake_case__				):  # If it is the right children
           _SCREAMING_SNAKE_CASE   :				Any							    = new_children
         else:
           _SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = new_children
       else:
         _SCREAMING_SNAKE_CASE   :				Any							    = new_children
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       if node.parent and node.parent.right:
         return node == node.parent.right
       return False
     def 				__SCREAMING_SNAKE_CASE							(     self				):




       """simple docstring"""


       return self.root is None
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				Optional[int]							    = Node(snake_case__				)  # create a new Node
       if self.empty():  # if Tree is empty
         _SCREAMING_SNAKE_CASE   :				str							    = new_node  # set its root
       else:  # Tree is not empty
         _SCREAMING_SNAKE_CASE   :				Dict							    = self.root  # from root
         if parent_node is None:
           return
         while True:  # While we don't get to a leaf
           if value < parent_node.value:  # We go left
             if parent_node.left is None:
               _SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = new_node  # We insert the new node in a leaf
               break
             else:
               _SCREAMING_SNAKE_CASE   :				int							    = parent_node.left
           else:
             if parent_node.right is None:
               _SCREAMING_SNAKE_CASE   :				str							    = new_node
               break
             else:
               _SCREAMING_SNAKE_CASE   :				Optional[int]							    = parent_node.right
         _SCREAMING_SNAKE_CASE   :				Any							    = parent_node
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     *snake_case__				):




       """simple docstring"""


       for value in values:
         self.__insert(snake_case__				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       if self.empty():
         raise IndexError("Warning: Tree is empty! please use another."				)
       else:
         _SCREAMING_SNAKE_CASE   :				Optional[int]							    = self.root
         # use lazy evaluation here to avoid NoneType Attribute error
         while node is not None and node.value is not value:
           _SCREAMING_SNAKE_CASE   :				List[Any]							    = node.left if value < node.value else node.right
         return node
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__ = None				):




       """simple docstring"""


       if node is None:
         if self.root is None:
           return None
         _SCREAMING_SNAKE_CASE   :				Optional[Any]							    = self.root

       if not self.empty():
         while node.right is not None:
           _SCREAMING_SNAKE_CASE   :				Dict							    = node.right
       return node
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__ = None				):




       """simple docstring"""


       if node is None:
         _SCREAMING_SNAKE_CASE   :				List[Any]							    = self.root
       if self.root is None:
         return None
       if not self.empty():
         _SCREAMING_SNAKE_CASE   :				Any							    = self.root
         while node.left is not None:
           _SCREAMING_SNAKE_CASE   :				Optional[int]							    = node.left
       return node
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				Dict							    = self.search(snake_case__				)  # Look for the node with that label
       if node is not None:
         if node.left is None and node.right is None:  # If it has no children
           self.__reassign_nodes(snake_case__  ,     snake_case__				)
         elif node.left is None:  # Has only right children
           self.__reassign_nodes(snake_case__  ,     node.right				)
         elif node.right is None:  # Has only left children
           self.__reassign_nodes(snake_case__  ,     node.left				)
         else:
           _SCREAMING_SNAKE_CASE   :				Dict							    = self.get_max(
               node.left				)  # Gets the max value of the left branch
           self.remove(tmp_node.value				)  # type: ignore
           _SCREAMING_SNAKE_CASE   :				List[Any]							    = (
               tmp_node.value  # type: ignore
           )  # Assigns the value to the node to delete and keep tree structure
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       if node is not None:
         yield node  # Preorder Traversal
         yield from self.preorder_traverse(node.left				)
         yield from self.preorder_traverse(node.right				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__=None				):




       """simple docstring"""


       if traversal_function is None:
         return self.preorder_traverse(self.root				)
       else:
         return traversal_function(self.root				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__				):




       """simple docstring"""


       if node:
         self.inorder(snake_case__  ,     node.left				)
         arr.append(node.value				)
         self.inorder(snake_case__  ,     node.right				)




     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				list[int]							    = []
       self.inorder(snake_case__  ,     snake_case__				)  # append all values to list using inorder traversal
       return arr[k - 1]





def    _lowerCAmelCase    (     lowerCamelCase__							:							Node | None				)  ->    list[Node]:
  _SCREAMING_SNAKE_CASE   :				Optional[int]							    = []
  if curr_node is not None:
    _SCREAMING_SNAKE_CASE   :				int							    = postorder(curr_node.left				) + postorder(curr_node.right				) + [curr_node]
  return node_list





def    _lowerCAmelCase    (     )  ->    None:
  _SCREAMING_SNAKE_CASE   :				Any							    = (8, 3, 6, 1, 1_0, 1_4, 1_3, 4, 7)
  _SCREAMING_SNAKE_CASE   :				List[Any]							    = BinarySearchTree()
  for i in testlist:
    t.insert(lowerCamelCase__				)

  # Prints all the elements of the list in order traversal
  print(lowerCamelCase__				)

  if t.search(6				) is not None:
    print("The value 6 exists"				)
  else:
    print("The value 6 doesn't exist"				)

  if t.search(-1				) is not None:
    print("The value -1 exists"				)
  else:
    print("The value -1 doesn't exist"				)

  if not t.empty():
    print("Max Value: ",						t.get_max().value				)  # type: ignore
    print("Min Value: ",						t.get_min().value				)  # type: ignore

  for i in testlist:
    t.remove(lowerCamelCase__				)
    print(lowerCamelCase__				)


if __name__ == "__main__":
      import doctest

      doctest.testmod(verbose=True)



