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.

13 Answers

▲

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.

▲

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.

▲

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

▲

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->left==p || root->right==p || root->left==q || root->right==q)

{

return(root);

}

else

{

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

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

if(l!=NULL && r!=NULL)

{

return(root);

}

else

{

tmp = (l!=NULL) ? l : r;

return(tmp);

}

}

}

▲

0

▼

Smiles, my ancestors don't sit in trees. - Do yours?

We have grown used to sitting under them and have great picnics...

▲

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

▲

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.

▲

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

▲

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->p; }

while (b) { qb.push(b); b = b->p; }

Node * result = NULL;

while (qa.top() == qb.top()) {

result = qa.top();

qa.pop();

qb.pop();

}

return result;

}

▲

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 && key > key2)

root = root.LeftChild;

else

return root;

}

return null;

}

▲

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.

▲

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.

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

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.