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.
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