Leave a comment

Non-recursive algorithm to find the pre-order successor of a given node in a BST

Question: Write a non-recursive algorithm to find the pre-order successor of a given node in a BST.

Solution:
Let me tell you the background first. There are basically three kind of traversal for a binary tree. Each traversal is named on the basis of processing of root node. For example in preorder traversal, root will be processed before any other node, in postorder, root will be processed only after all the nodes are processed.

Following is the order of processing in each traversal:
    Pre-Order: root–>left–>right
    Post-Order: left–>right–>root
    In-Order: left–>root–>right
When I say left/right, it means left/right sub tree and not just the child node.

Now back to our main problem. If you look at pre-order traversal given above, we can easily find out the pre-order successor of an internal node. But, problem comes when it is a leaf node. Look at the pre-order traversal again, according to it, once you reach at any leaf node, you have to go to right sub tree of an ancestor which is not yet processed. So, root of that right sub tree will be the pre-order successor of that leaf node which you are considering at any point of time.

Please find the algorithm herein below:

  1. if given node is not present, return null
  2. if node has left child, return left child
  3. if node has right child, return right child
  4. return right child of the closest ancestor whose right child is present and not yet processed

I have implemented the code for the same algorithm, find it below:

public static BST getPreorderSuccessor(BST root, int val){
    if( root == null || (root.getLeft() == null && root.getRight() == null))
        return null;
    BST temp = root;
    BST ancestor = null;
    while(temp != null && temp.getVal() != val){
        if(val < temp.getVal()){
            if(temp.getRight() != null){
                ancestor = temp;
            }
            temp = temp.getLeft();
        }else{
            temp = temp.getRight();
        }
    }
    // node not found case
    if(temp == null)
        return null;
    if(temp.getLeft() != null)
        return temp.getLeft();
    if(temp.getRight() != null)
        return temp.getRight();
    if(ancestor != null)
        return return ancestor.getRight();
    return null;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: