Amazon Interview Question: Find the deepest common ances... | Glassdoor

## Interview Question

Software Development Engineer Interview Seattle, WA

# Find the deepest common ancestor of two nodes in a tree

structure.
Tags:
tree, binary search tree, bst

7

This interview was frustrating because it felt like the woman couldn't write code in C++. I first asked whether I could assume a standard Tree node structure (as I've built several custom structures and they all have many of the same basic components) and she was pretty much dumbstruck and told me ti write the implementation for one. So i did. Then I started walking through my solution and practically had to spell the word iterator when I said I declared one. My solution was basically to just descend in the tree toward the first value until the two values are on different sides of the current node or you fall out the bottom of the tree. I had to repeat the conditional statements character by character for the interviewer.

Interview Candidate on Oct 15, 2009
2

Isn't the root node always the "deepest" common ancestor? Either the question is worded wrong, or you answered it incorrectly, but I think it's most likely that it's worded wrong.

mliu on Nov 17, 2009
10

@mliu
the question is correct. u r thinking wrong.
depth of a tree grows towards its leaves.
root is the least deep node in a tree.

nunnu on Dec 19, 2009
0

@nunnu is right here what the question wanted was the common ancestor furthest from the root. Again, I'm pretty sure (by subsequent conversations with friends) that my answer was right but that the interviewer and I just couldn't communicate

Candidate (alanbly) on Dec 19, 2009
1

struct node
{
int value;
struct node *right;
struct node *left;
}mynode;

mynode *closestAncestor(mynode* root, mynode* p, mynode* q)
{
mynode *l, *r, *tmp;

if(root == NULL)
{
return(NULL);
}

if(root-&gt;left==p || root-&gt;right==p || root-&gt;left==q || root-&gt;right==q)

{
return(root);
}
else
{
l = closestAncestor(root-&gt;left, p, q);
r = closestAncestor(root-&gt;right, p, q);

if(l!=NULL &amp;&amp; r!=NULL)
{
return(root);
}
else
{
tmp = (l!=NULL) ? l : r;
return(tmp);
}
}
}

Anonymous on Mar 21, 2010
0

Smiles, my ancestors don't sit in trees. - Do yours?
We have grown used to sitting under them and have great picnics...

Tess on Oct 4, 2010
6

Suppose we need to find common ancestor for the nodes with values A an B.
start from the root and compare value of the root node with both A and B. If A an B are both below/above the node's value then go down to the next node. Repeat until we find a node where A and B "go" to different links. This node seems to be 'common ancestor'.

Andrew on Nov 9, 2010
0

Traverse up the tree for both the nodes and add them to the explored list. If there is a common element in the explored list of both the nodes, that's the common ancestor.

Hari on Feb 20, 2011
0

Hari, if the answer was the root your approach would have n^2*lg(n) complexity where mine had lg(n) in the worst case

Candidate on Feb 20, 2011
0

solution with O(h) time and memory complexity (h - height of the tree)

Node * dca(const Node * a, const Node * b) {
stack qa, qb;

while (a) { qa.push(a); a = a-&gt;p; }
while (b) { qb.push(b); b = b-&gt;p; }
Node * result = NULL;
while (qa.top() == qb.top()) {
result = qa.top();
qa.pop();
qb.pop();
}
return result;
}

Marcin on Dec 25, 2011
2

To find the common ancestor. O(lg N)

public Node GetCommonParent(Node root, int key1, int key2)
{
while (root != null)
{
int key = root.iData;
if (key key1 &amp;&amp; key &gt; key2)
root = root.LeftChild;
else
return root;
}

return null;
}

Joarder on Jan 6, 2013
1

@Joarder: your answer is both really bad coding practice and only works for very specifically-structured trees (binary search trees based in integer keys). The approach is a good one, but you should not override a parameter being passed in and you should use Node.isLeft(Node) and Node.isRight(Node) rather than comparing keys directly. Remember that a tree can be made from a collection of any comparable object, keys are not required.

Candidate on Jan 7, 2013
0

Why was the first answer down voted? I think thats the best answer.. There is no better way.. And its O(log n) complexity.

Anonymous on May 2, 2015