Home > Applied Algorithms, Recursion, Tree > Find the lowest common ancestor of two given nodes in a tree.

Find the lowest common ancestor of two given nodes in a tree.

This question was pretty much a favorite at my Microsoft interviews. Interviews were asking this one left and right. The only bit of tricky part is that you cannot assume that the tree has back-pointers. Take  a binary tree with pointers pointing from parent to children. That is it.

So what do you think is the best way to do this? I mentioned in the post where we found the depth of the tree using recursion that it is the best way to deal with trees which aren’t too huge. This is the very same. You can once again recurse to the leaf nodes. Then start moving up and return 1 when you find one of the two given nodes or when the value you are receiving from the left or right side is 1. Here, 1 indicates that one of the nodes has been found somewhere beneath that point. So the node where you get a 1 from both left and right sides, is the node you want!

Hope you got that logic. If not, here is a pseudo-code. Perform a dry run for any tree and see how things work out :

int ancestor (node * curr,  node * node1, node * node2) //curr will be root for the first time

{

if(node1==node2)

{

PRINT “BOTH NODES SAME”;

}

if (curr->left NOT equal to NULL)

{

int l = ancestor (curr->left, node1, node2);

}

if (curr->right NOT equal to NULL)

{

int r = ancestor (curr->right, node1, node2);

}

if(curr-> right EQUAL to NULL and curr->left EQUAL to NULL)

{//leaf node

if(curr == node1 or curr=node2)

return 1;

else

return 0;

}

if (l+r ==2)

{

PRINT “YOU FOUND YOUR NODE”;

//do the needful

}

if(curr == node1 OR curr=node2)

{

return l+r+1;

}

return l+r;

}

Now that was a simple code. If you didn’t get anything, the comments are always open.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

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: