|
Given a tree where each node points to its parent ......
Microsoft Interview Questions and Answers
(Continued from previous question...)
139. Given a tree where each node points to its parent ......
Question:
Given a tree where each node points to its parent, find LCA of two nodes. Write test cases for same.
maybe an answer:
node* LCA(node *x,node *y)
{
int d1=0,d2=0;
for(node *i=x;i!=NULL;i=i->parent) d1++;
for(node *i=y;i!=NULL;i=i->parent) d2++;
if(d1!=d2)
{
while(d1<d2) {
y=y->parent;
d2--;
}
while(d1>d2) {
x=x->parent;
d1--;
}
}
while(x!=y)
{
x=x->parent;
y=y->parent;
}
return x;
}
(Continued on next question...)
Other Interview Questions
| 