Binary_Search_Tree.py

class Binary_Search_Tree:
  # TODO.I have provided the public method skeletons. You will need
  # to add private methods to support the recursive algorithms
  # discussed in class

  class __BST_Node:
    # TODO The Node class is private. You may add any attributes and
    # methods you need. Recall that attributes in an inner class 
    # must be public to be reachable from the the methods.

    def __init__(self, value):
      self.value = value
      self.height = 1
      self.right = None
      self.left = None
    #O(1): Just initalizing the node class

  def __init__(self):
    self.__root = None
  #O(1): Just initalizing the BST class

  def insert_element(self, value):
    # Insert the value specified into the tree at the correct
    # location based on "less is left; greater is right" binary
    # search tree ordering. If the value is already contained in
    # the tree, raise a ValueError. Your solution must be recursive.
    # This will involve the introduction of additional private
    # methods to support the recursion control variable.
    self.__root = self.__recursive_insert(value, self.__root)
  # O(log(n)): This function returns an O(log(n)) function

  def __recursive_insert(self, val, root):
    if root is None:
      return self.__BST_Node(val)
    elif root.value==val:
      raise ValueError
    else:
      if root.value < val:
        root.right = self.__recursive_insert(val, root.right)
      if root.value > val:
        root.left = self.__recursive_insert(val, root.left)
      return self.__balance(root)
  # O(log(n)): Traversal of a balanced tree recursively to find an element is O(log(n)) because the height is O(log(n)), 
  # and then you may have to call balance once while returning roots but it is a constant time operation so the function is O(log(n))

  def remove_element(self, value):
    # Remove the value specified from the tree, raising a ValueError
    # if the value isn't found. When a replacement value is necessary,
    # select the minimum value to the from the right as this element's
    # replacement. Take note of when to move a node reference and when
    # to replace the value in a node instead. It is not necessary to
    # return the value (though it would reasonable to do so in some 
    # implementations). Your solution must be recursive. 
    # This will involve the introduction of additional private
    # methods to support the recursion control variable.
    self.__root = self.__recursive_delete (value, self.__root)
  # O(log(n)): This function returns an O(log(n)) function
  
  def __recursive_delete(self,val,root):
    if root is None:
      raise ValueError
    elif val < root.value:
      root.left = self.__recursive_delete(val, root.left)
    elif val > root.value:
      root.right = self.__recursive_delete(val, root.right)
    else:
      if root.right is None:
        return root.left
      elif root.left is None:
        return root.right
      else:
        min_right = self.__find_right_min(root.right)
        root.value = min_right.value
        root.right = self.__recursive_delete(root.value, root.right)
    return self.__balance(root)
  # O(log(n)): Traversal of a balanced tree recursively to find an element is O(log(n)) because the height is O(log(n)), 
  # and then you may have to call find_right_min which is O(log(n)) but only once and just to traverse the rest of the
  # height of the tree, and then balance may be called multiple times but it is a constant time operation so the function is O(log(n))
  
  def __find_right_min(self, root):
    if root.left is None:
     return root
    return self.__find_right_min(root.left)
  # O(log(n)): The tree is balanced so the height is log(n), so the furthest traversal to find the right min
  # is through the height of the tree, or log(n)
  
  def __balance(self, root):
    balance = (root.right.height if root.right else 0)-(root.left.height if root.left else 0)
    if balance == -1 or balance == 0 or balance == 1:
      root.height = self.__calculate_height(root)
      return root
    if balance == -2:
      if (root.left.right.height if root.left.right else 0)-(root.left.left.height if root.left.left else 0) == 1:
        root.left = self.__rotate_left(root.left)
      return self.__rotate_right(root)
    if balance == 2:
      if (root.right.right.height if root.right.right else 0)-(root.right.left.height if root.right.left else 0) == -1:
        root.right = self.__rotate_right(root.right)
      return self.__rotate_left(root)
  # O(1): Balance method does some calculations from stored heights, and then some rotations which are 0(1) methods. 
  # May be called multiple times in a deletion, but the actual method is O(1)

  def __rotate_right(self,root):
    old_root = root
    new_root = root.left
    middle_tree = root.left.right
    new_root.right = old_root
    old_root.left = middle_tree
    old_root.height = self.__calculate_height(old_root)
    new_root.height = self.__calculate_height(new_root)
    return new_root
  # O(1): Re-assignment statements and then calling an O(1) method exactly twice
  

  def __rotate_left(self,root):
    old_root = root
    new_root = root.right
    middle_tree = root.right.left
    new_root.left = old_root
    old_root.right = middle_tree
    old_root.height = self.__calculate_height(old_root)
    new_root.height = self.__calculate_height(new_root)
    return new_root
  # O(1): Re-assignment statements and then calling an O(1) method exactly twice
  
  def __calculate_height(self, root):
    return 1 + max(root.left.height if root.left else 0, root.right.height if root.right else 0)
  # O(1): A simple calculation using stored heights
  
  def get_height(self):
    # return an integer that represents the height of the tree.
    # assume that an empty tree has height 0 and a tree with one
    # node has height 1. This method must operate in constant time.
    if self.__root is None:
      return 0
    else:
      return self.__root.height
  # O(1): Returning a stored value (or 0), so constant time

  def in_order(self):
    # Construct and return a string representing the in-order
    # traversal of the tree. Empty trees should be printed as [ ].
    # Trees with one value should be printed as [ 4 ]. Trees with more
    # than one value should be printed as [ 4, 7 ]. Note the spacing.
    # Your solution must be recursive. This will involve the introduction
    # of additional private methods to support the recursion control 
    # variable.
    if self.__root is None:
      return '[ ]'
    traversal = []
    self.__recursive_in_order(self.__root, traversal)
    return '[ ' + ', ' .join(map(str, traversal)) + ' ]'
  # O(n): Calls an O(n) function, and join is also O(n), but these elements are not within one another, so
  # the function is just O(n) multiplied by a constant so O(n) 

  def __recursive_in_order(self, root, traversal):
    if root is None:
      return
    else:
      self.__recursive_in_order(root.left, traversal)
      traversal.append(root.value)
      self.__recursive_in_order(root.right, traversal)
  # O(n): must traverse though every value in the tree (recursively), meaning that with more elements, the fuction is recursively
  # called more times
        
  def pre_order(self):
    # Construct and return a string representing the pre-order
    # traversal of the tree. Empty trees should be printed as [ ].
    # Trees with one value should be printed in as [ 4 ]. Trees with
    # more than one value should be printed as [ 4, 7 ]. Note the spacing.
    # Your solution must be recursive. This will involve the introduction
    # of additional private methods to support the recursion control 
    # variable.
    if self.__root is None:
      return '[ ]'
    traversal = []
    self.__recursive_pre_order(self.__root, traversal)
    return '[ ' + ', '.join(map(str, traversal)) + ' ]'
  # O(n): Calls an O(n) function, and join is also O(n), but these elements are not within one another, so
  # the function is just O(n) multiplied by a constant so O(n) 
  
  def __recursive_pre_order(self, root, traversal):
      if root is None:
        return
      else:
        traversal.append(root.value)
        self.__recursive_pre_order(root.left, traversal)
        self.__recursive_pre_order(root.right, traversal)
  # O(n): must traverse though every value in the tree (recursively), meaning that with more elements, the fuction is recursively
  # called more times

  def post_order(self):
    # Construct an return a string representing the post-order
    # traversal of the tree. Empty trees should be printed as [ ].
    # Trees with one value should be printed in as [ 4 ]. Trees with
    # more than one value should be printed as [ 4, 7 ]. Note the spacing.
    # Your solution must be recursive. This will involve the introduction
    # of additional private methods to support the recursion control 
    # variable.
    if self.__root is None:
      return '[ ]'
    traversal = []
    self.__recursive_post_order(self.__root, traversal)
    return '[ ' + ', '.join(map(str, traversal)) + ' ]'
  # O(n): Calls an O(n) function, and join is also O(n), but these elements are not within one another, so
  # the function is just O(n) multiplied by a constant so O(n) 
  
  def __recursive_post_order(self, root, traversal):
      if root is None:
        return
      else:
        self.__recursive_post_order(root.left, traversal)
        self.__recursive_post_order(root.right, traversal)
        traversal.append(root.value)
  # O(n): must traverse though every value in the tree (recursively), meaning that with more elements, the fuction is recursively
  # called more times

  def to_list(self):
    # Construct and return a Python list/array containing the in-order
    # traversal of the tree. Your solution must be recursive. This will
    # involve the introduction of additional private methods to support
    # the recursion control variable.
    traversal = []
    self.__recursive_in_order(self.__root, traversal)
    return traversal
  # O(n): recursive_in_order is called and it is an O(n) function, so to_list is also O(n)

  def __str__(self):
    return self.in_order()
  # O(n): Returns an O(n) function, so it is also O(n)
  

if __name__ == '__main__':
  pass