## Amazon Interview Question

Software Engineer / Developers**Country:**United States

this code doesn't work if n1<root and n2>root..

if(n1.value<root.value && n2.value<root.value)

return root;

Girish:

is the case you have mentioned taken care of by the last return statement "return root".

n1.value < root.value && n2.value < root.value .. one check would suffice.. rest is ok..

This code only seems to be working for leaf nodes. In case one of the node to be checked is itself a parent of some other then this will give wrong result. Please correct me if wrong.

//to search for common ancestor in a binary tree, the code would be

treeNodePtr findLCA(treeNodePtr root, int p, int q) {

// no root no LCA.

if(!root) {

return NULL;

}

// if either p or q is the root then root is LCA.

if(root==p || root==q) {

return root;

} else {

// get LCA of p and q in left subtree.

treeNodePtr l=findLCA(root->left , p , q);

// get LCA of p and q in right subtree.

treeNodePtr r=findLCA(root->right , p, q);

// if one of p or q is in leftsubtree and other is in right

// then root it the LCA.

if(l && r) {

return root;

}

// else if l is not null, l is LCA.

else if(l) {

return l;

} else {

return r;

}

}

}

nice solution, with the only constraint that the algorithm will give wrong answer if p or q do not exist in the tree.

This is a fairly common question that is asked in many interviews. Refer to the Lowest Common Ancestor tutorial on TopCoder.

I found the last method(using the Euler Tour method to traverse the graph) more easier to understand than the other methods mentioned in the tutorial.

Do a pre order traversal of tree. Scan the list of nodes obtained by pre order traversal. In this list a node which is last such node which was visited before these 2 nodes should be common ancestor.

This should work for for binary tree and binary search tree.

For a BST this is very easy and Vijay has given the right algorithm.

For a binary tree you can calculate the list of nodes from the root to a particular node.

Do this for both the nodes. Compare their list of ancestors. The last element of the longest matching prefix is the LCA. Very simple.

(nobrainer .co .cc)

I am assuming you are looking for the *least* common ancestor.

2. binary search tree

- vijay January 14, 2012