Interview Question
Hey thanks for the answer:
Just one small doubt:
if (fFoundInLeft) ||fFoundInRight)
{
if ((r->v == v1) || (r->v == v2))
print ("found LCA = %x", r);
return TRUE;
}
IMO this will hit only when either of v1 or v2 is root, in that case we should return LCA not found or are we considering a node is a ancestor of itself.
Also about the complexity analysis the complexity is O(n). Isnt it possible to give a solution with o(logn) complexity.
For example we can use marking algorithm:
1) traverse from v1 to root and mark every node.
2) then traverse from v2 to root and the first marked node is our LCA if the marked node is not v1.
3) or else parent of v1 will be LCA.
Step1 Get Inorder traversal of binary tree
Step2 LCS(Node *root,int Val1,int Val2)
Step3 If(Val1 and Val2 occur before root in inorder traversal)
then LCS(root->Left,val1,val2)
else if(both Val1 and Val2 occur to the right of root in inorder traversal)
then LCS(root->right,val1,val2)
else if(both val1 and val2 are present in binary tree)
then return root
else print(NO COMMON ANCESTOR AS VALUES ARE NOT PRESENT IN THE TREE)
Comments over the solution will be highly appreciated.
What if one of the values is 2 or 3 levels down the current level in the left..?? how would it work then. What you have suggested might work for binary Search Tree, i doubt if this would work for a simple binary tree...
- MS June 02, 2010bool LCA (node *r, int v1, int v2) { if (r == NULL) return FALSE; BOOL fFoundInLeft = LCA (r->left, v1, v2); BOOL fFoundInRight = LCA (r->right, v1, v2)) if (fFoundInLeft && fFoundInRight) { print ("found LCA = %x", r); return TRUE; } if (fFoundInLeft) ||fFoundInRight) { if ((r->v == v1) || (r->v == v2)) print ("found LCA = %x", r); return TRUE; } if ((r->v == v1) || (r->v == v2)) return TRUE; return FALSE; }