JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Lowest Common Ancestor Revision History (1 edit)
Lowest Common Ancestor
I wish to ask if this problem can be done in the following way:

Let the two nodes whose LCA is asked be N1 and N2

Let their levels in the tree be L(N1),L(N2) let L(N1)>L(N2)

i=L(N1)-L(N2);
p=N1;
while(i)
{
p=father(p);
i--;
}

q=n2;
while(father(p)!=NULL)
{
if(p==q)
return p;

p=father(p);
q=father(q);
}

plz do reply at arora.gaurav.8690@gmail.com
Lowest Common Ancestor
I wish to ask if this problem can be done in the following way:

Let the two nodes whose LCA is asked be N1 and N2

Let their levels in the tree be L(N1),L(N2) let L(N1)>L(N2)

i=N1-N2
p=N1;
while(i)
p=father(p);

q=n2;
while(father(p)!=NULL)
{
if(p==q)
return p;

p=father(p);
q=father(q);
}

plz do reply at arora.gaurav.8690@gmail.com