Adobe Interview Question
Computer ScientistsCountry: India
Interview Type: Written Test
But with a node how can you go upwards in binary tree. Does you tree structure will store a link to its parent node also ?
Suppose the tree is -
20
/ \
10 30
/ \
5 17
/ \
1 7
and we need to find out the common ancestor of node 1 and node 17.
1. Then first of all compute the smallest node . In our case its 1.
2. After that traverse upward (Please note in my node there is also a pointer to the parent node.) till we get the last ancestor which is greater than the other node(i.e Node 17).
3. Return the last ancestor which is greater than the other node(i.e Node 17) which is the desired result.
There is an unique propriety for the common ancestor for two node in a BST,
The value of ancestor node must be in the middle of the two node, while the parent of the lowest common ancestor must be either both greater than or less than both node(if there is a parent node for the common ancestor).
The reason is if there is a node on the ancestor path is either greater or less then both given nodes, then, the two node must lay on the same side of that ancestor's sub tree, which means it could not be the lowest common ancestor.
If we follow down the path, till there is a node whose value is in the middle the two node, then, the two node must lay on different sub tree of that node.
Using this propriety, should be very easy to find the common ancestor.
Cheers!
This problem could be solved by using X-OR operation.
1. store address in left link of node is X-OR (parentNodeAddress,LeftNodeaddress) and similarly for right.
2. in this way at a given node by performing X-OR we can get parent node.
3. In this way we can find LCA by O(n) time without knowing root address.
In this problem i assume parents address is given & the idea is just to find the intersection of two lines .....
The phsedo code is like this :
struct node* LCA(struct node* a, struct node* b){
int height1 = get_height(a);
int height2 = get_height(b);
int Dy = abs(height1-height2);
if (height1>height2) {
for(int i =Dy;i>=0;i--)
a = a->parents;
while(a!=b) {
a = a->parents;
b = b->parents;
}
return a;
} else if (height1<height2) {
// same as above....
}
}
I hope the code is clear, if any issue let me know.
I am assuming that the node-parent relationship is provided (we know that the root of the tree is not given).
struct bst *LCA(struct bst *n1, struct bst *n2)
{
if(n1==NULL && n2==NULL)
return NULL;
else if(n1==NULL || n2==NULL)
return NULL;
else if(n1==n2)
return n1;
else
{
if(n1->data < n2->data)
return LCA(n1,n2->parent);
else if(n2->data<n1->data)
return LCA(n1->parent,n2);
}
return NULL;
}
If the parent-child relationship is known, we use a hash table:
while(n1!=NULL)
{
hash_table[n1]=1;
n1=n1->parent;
}
while(n2!=NULL)
{
if(hash_table[n2]==1)
return n2;
n2=n2->parent;
}
return NULL;
We can also use the data stored in each node to hash the values. The caveat with this latter approach is it cannot handle the duplicates.
This question is exactly similar to another popular question "Given two singly linked lists and they both intersect at one point (ie, forming a Y shaped list). Find where the two linked lists merge"
So we can simply boil down this question to simple question.
// As root->parent is NULL, we don't need to pass root in.
Node *LCA(Node *p, Node *q) {
int h1 = getHeight(p);
int h2 = getHeight(q);
// swap both nodes in case p is deeper than q.
if (h1 > h2) {
swap(h1, h2);
swap(p, q);
}
// invariant: h1 <= h2.
int dh = h2 - h1;
// coming the deeper node to the same level w.r.t. root
for (int h = 0; h < dh; h++)
q = q->parent;
//At same level
while (p && q) {
if (p == q) return p;
p = p->parent;
q = q->parent;
}
return NULL; // p and q are not in the same tree
}
if each node in tree has pointer to it's parent, then we can find the LCA even if tree's root is not given. In this case this problem will be similar to finding intersection of two linked list.
- OTR August 10, 2013keep traversing two nodes separately till parent is null. this way we can find the length of these two lists. get the difference of these two lengths and in bigger list , traverse till this length difference, and after that keep moving forward in these two list and compare the parent nodes.
When parent node is same that node will be LCA.
This can also be solved using two stacks. Keep putting parent node of each given node on stack till parent node is null. pop each node from stack and compare, if they are same then keep popping, when the node is different, then that node is LCA.