# 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