Delete from BST
by Isai Damier

  #=====================================================================
  # Author: Isai Damier
  # Title: Delete
  # Project: geekviewpoint
  # Package: algorithms
  #
  # Time Complexity of Solution:
  #   Best = const; Average = O(log(n)); Worst = O(n).
  #
  # Technical Details:
  #    1] find node to be removed and track its parent
  #    2] if node is None then return None (element is not in tree)
  #    3] declare 'replacement' Node
  #    4] if node has both children
  #     - delete node's successor
  #     - give custody of node's children to successor
  #     - set 'replacement' to successor
  #    5] if node has fewer than two children
  #     - set 'replacement' to node's child
  #    6] if node is self.root then set 'replacement' to self.root
  #       (new self.root)
  #    7] else 'replacement' becomes child of node's parent
  #
  #=====================================================================
 
 class BST( object ):

  def __init__( self ):
      self.root = None


  def getRoot( self ):
    return self.root

  def delete( self, el ):
    # find node and it's parent
    node, parent = self.root, None

    while node is not None and el != node.data:
      parent = node
      if el > node.data:
        node = node.right
      else:
        node = node.left

    # if node is None return None
    if node is None:
      return None

    # declare replacement
    replacement = None
    # if node has two children
    if node.left is not None and node.right is not None:
      replacement = self.removeSuccessor( node )
      replacement.left = node.left
      replacement.right = node.right
    # if node has one or no child
    elif node.left is None:
      replacement = node.right
    else:
      replacement = node.left

    # replace node
    if node == self.root:
      self.root = replacement
    elif parent.left == node:
      parent.left = replacement
    else:
      parent.right = replacement

    return node


  def removeSuccessor( self, n ):
    # it is known that n has a right child
    succ, parent = n.right, n
    while succ.left is not None:
      parent = succ
      succ = succ.left

    # a successor has no left child
    if succ == parent.right:
      parent.right = succ.right
    else:
      parent.left = succ.right

    return succ