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