Successor

Write an algorithm to find the “next” node of a given node in a binary search tree. You may assume that each node has a link to its parent.

Solution

There are two scenarios we need to consider. If the node has a right child, the successor will be the leftmost node in the right child tree. If the node has no right child, the successor will be the parent tree of which the node is a left child.

Let’s consider the first scenario first. This traversal is fairly straight forward - we need to recurse down the left children in the tree.

def traverse_left(node):
  if(node.left != None):
    return traverse_left(node.left)
  else:
    return node.key

The second scenario is slightly more complicated. We need to traverse upward until we reach a parent node from its left child.

def traverse_up(node):
  if (node.parent != None) and (node.parent.left == node):
    return node.parent
  elif (node.parent != None) and (node.parent.right == node):
    return traverse_up(node.parent)
  elif (node.parent == None):
    return None

Finally, we can stitch these two together in a single function.

def find_successor(node):
  if(node.right != None):
    successor = traverse_left(node.right)
  elif(node.parent != None):
    successor = traverse_up(node)
  else:
    successor = None

  if(successor == None):
    return node
  else:
    return successor