wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Least Common Ancestor
        
(Message started by: kanagavel_india on Feb 14th, 2006, 10:39pm)
Title: Least Common Ancestor
Post by kanagavel_india on Feb 14th, 2006, 10:39pm
Hi,
Anybody having a best solution to find Least Common ancestor for two elements in a binary tree.,

Regards
Kanagavel A
Title: Re: Least Common Ancestor
Post by towr on Feb 15th, 2006, 12:13am
Depending on your needs, there are several possible bests.

Is it a regular tree, or a binary search tree?
Can we have extra information at each node (such as at which level in the tree the node is)?
Title: Re: Least Common Ancestor
Post by kanagavel_india on Feb 15th, 2006, 1:16am
For BST, it is quite simple,
To find a LCA for x and y
INPUT : ROOT, x,y

int LCA(Root,x,y)
{
  if(Root->data within the range x and y)return Root->data
  if(x,y both > Root->data) return(LCA(Root->right,x,y))
  else if(x,y both < Root->data) return(LCA(Root->left,x,y))
}




But I need solution for Binary tree... And Each node can contain only left / right child pointer and data


Regards
Kanagavel A
Title: Re: Least Common Ancestor
Post by towr on Feb 15th, 2006, 1:53am
Hmm, so you don't even have a pointer to the parent? I'm pretty sure that rules out an O(n) solution (where n is the maximum of the depth of both nodes).
You can of course use DFS to find a path to both nodes, and then find the last common node in that path. But that's linear in the number of nodes in the entire tree.
Title: Re: Least Common Ancestor
Post by kanagavel_india on Feb 15th, 2006, 2:19am
Hi towr,

Can u explain how to implement ur solution...
Title: Re: Least Common Ancestor
Post by towr on Feb 15th, 2006, 3:28am
Well, basicly what you need is a depth first search (or breadth first search) function that returns the path to a node you look for.
Find the paths for the two nodes you want the least common ancestor for.
Then compare the two path, and find the last common element.


Code:
listnode* DFSpathfinder(treenode * root, treenode * target)
{
 if (root==target)
   return new listnode(root, null);

 listnode* next;
 if (next  = DFSpathfinder(root->left, target))
   return new listnode(root, next);
 else if (next = DFSpathfinder(root->right, target))
   return new listnode(root, next);
 else return null;
}

treenode* LCA(treenode * root, treenode * desc1,  treenode * desc2)
{
 listnode *path1, *path2;
 path1 = DFSpathfinder(root, desc1);
 path2 = DFSpathfinder(root, desc2);

 while ( (path1->next) || (path1->next->data == path2->next->data) )
 {
   path1=path1->next;
   path2=path2->next;
 }
 return path1->data;
}

This code comes with the guarantee it won't compile (I haven't defined a listnode class for one). But it should give you an idea about what I'm trying to do.
Title: Re: Least Common Ancestor
Post by kanagavel_india on Feb 15th, 2006, 3:40am
Nice Solution, Thanks a lot..,

But in many of interviews, they wont allow to use such a huge memories, In your solution, u r using two list to store paths, It take a large mem if the depth of the tree is large..,

Can you give some other ways to avoid such a huge memories.,

I expect a solution without using huge extra memory
Title: Re: Least Common Ancestor
Post by towr on Feb 15th, 2006, 4:10am
Compared the the tree, the memory usage is on average just the 2log of it.

Without extra memory, you may be looking at a quadratic runtime. My first guess would be to look for the last subtree that contains both nodes, its root will be the LCA.

Any recursive search for a node will use more memory than storing the path btw, because of the execution stack. And it is difficult to get iteration to work on trees.
Title: Re: Least Common Ancestor
Post by shallow on Apr 25th, 2006, 6:52am
To find the LCA for A and B:

if B is deeper than B then find B's anceter until it is at the same level of A; similarly if A is deeper than B. then we can climb the tree to find the ancester of A and B at the same time. so it needs no extra space and can be finished with in O(n) time. n is the depth of the tree.
Title: Re: Least Common Ancestor
Post by KWillets on May 1st, 2006, 11:13am
This is a well-know problem, but I can summarize.

[hideb]
The LCA of a and b is the node with minimal depth on the path from a to b.

Perform an Euler tour (DFS) of the tree which outputs the depth of each node, on each visit (3 per node).  The path from a to b is a subrange of this sequence, and the LCA is the node in this subrange with minimal depth (the range minimum).  

The range-min problem can be optimized quite a bit, by recording range-min's for various intervals during pre-processing, and then at query time reducing the given interval to a union of precalculated subintervals.

Here's a better description: http://theory.lcs.mit.edu/classes/6.897/spring03/scribe_notes/L11/lecture11.pdf
[/hideb]
Title: Re: Least Common Ancestor
Post by Ved on Jan 22nd, 2010, 10:47pm

on 05/01/06 at 11:13:53, KWillets wrote:
This is a well-know problem, but I can summarize.

[hideb]
The LCA of a and b is the node with minimal depth on the path from a to b.

Perform an Euler tour (DFS) of the tree which outputs the depth of each node, on each visit (3 per node).  The path from a to b is a subrange of this sequence, and the LCA is the node in this subrange with minimal depth (the range minimum).  

The range-min problem can be optimized quite a bit, by recording range-min's for various intervals during pre-processing, and then at query time reducing the given interval to a union of precalculated subintervals.

Here's a better description: http://theory.lcs.mit.edu/classes/6.897/spring03/scribe_notes/L11/lecture11.pdf
[/hideb]


What about this ?
1. Find the path to both the nodes A and B from the root and store them in two arrays.
2. Last common value in these two arrays is the LCA

E.g : for the tree :
...........................1
......................2....|.....3
......................|
..................|.......|
..................4......5
...........................|
......................|.........|
......................6........7
we need to find LCA for 4 and 7, we store paths
as follows :
p1 = 1-2-5-7
p2 = 1-2-4
The last common number in these array is the LCA.
P.S : Sorry for the unpardonable formatting of the tree here.  :o
Title: Re: Least Common Ancestor
Post by Grimbal on Jan 23rd, 2010, 8:00am
@Ved: that is in other words what towr proposed.  It should work.
Title: Re: Least Common Ancestor
Post by bmudiam on Jan 23rd, 2010, 11:22am
Sorry for hijacking the thread.

Is it possible to do some kind of pre-processing and then return LCA for any two nodes in a binary tree in constant time? What kind of data structure will be used to store this info. Assuming, you are not allowed to modify the original binary tree.

I think this problem arises in operating systems, where, to move a directory structure from one directory to another directory, you need to lock the LCA so that LCA is not modified during the move.

I don't know how it is done currently. But I think, pre-processing can help in this scenario.
Title: Re: Least Common Ancestor
Post by Aryabhatta on Jan 23rd, 2010, 2:10pm

on 01/23/10 at 11:22:31, bmudiam wrote:
Sorry for hijacking the thread.

Is it possible to do some kind of pre-processing and then return LCA for any two nodes in a binary tree in constant time? What kind of data structure will be used to store this info. Assuming, you are not allowed to modify the original binary tree.

I think this problem arises in operating systems, where, to move a directory structure from one directory to another directory, you need to lock the LCA so that LCA is not modified during the move.

I don't know how it is done currently. But I think, pre-processing can help in this scenario.


It is possible to preprocess in O(n) time to answer LCA queries in O(1) time. Lookup RMQ and LCA on the web.

Also, KWillets has posted to this thread with a link. I am guessing that has what you need.
Title: Re: Least Common Ancestor
Post by Ved on Jan 24th, 2010, 2:00am

on 01/23/10 at 08:00:48, Grimbal wrote:
@Ved: that is in other words what towr proposed.  It should work.

Ah yes..I totally missed that. I am not able to generate the two paths though.
-----------------------------------------

Code:
private static void fillPaths(Node node){
       if(node == null)
       {
           return;
       }
       else
       {
           path1.add(node.data);
           path2.add(node.data);
           if (node.left != null)
               path1.add(node.left.data);

           if(node.right != null)
               path2.add(node.right.data);

           fillPaths(node.left);
           fillPaths(node.right);
       }
   }

-------------------------------------------------
Ofcourse this is not doing the job - need to get the DFS right.
Title: Re: Least Common Ancestor
Post by R on Jan 24th, 2010, 1:18pm

on 02/15/06 at 03:40:37, kanagavel_india wrote:
It take a large mem if the depth of the tree is large..,

Can you give some other ways to avoid such a huge memories.,

You can use bits of an integer to save the path. And if the depth of the nodes is <32 (size of integer in bits), a single integer would do your job.
Otherwise you will have to have an array of integers to save paths. One integer can save information of 32 nodes.
Title: Re: Least Common Ancestor
Post by serenity on Feb 12th, 2010, 2:11am
it is least common or lowest common ancestor ??  ::)
Title: Re: Least Common Ancestor
Post by RamRaul on Feb 12th, 2010, 9:08am
I hv come out with a simpler code...hope this works 8)

Node* LCA(Node *Root,Node* P,Node* Q)
{
 if(Root == NULL)
       return NULL;

 if(Root->left == P || Root->right == Q|| Root->left == Q || Root->right == P)
     return Root;

 Node *nleft= LCA(Root->left,P,Q);
 Node *nright = LCA(Root->right,P,Q);
 
 if(nleft!=NULL &&  nright!=NULL)
       return Root;
 else
   return (nleft== NULL)?nright:nleft;
}
Title: Re: Least Common Ancestor
Post by Grimbal on Feb 12th, 2010, 10:01am

on 02/12/10 at 09:08:30, RamRaul wrote:
...hope this works 8)

Er... it won't.


Quote:
if(Root->left == P || Root->right == Q|| Root->left == Q || Root->right == P)
     return Root;

You probably meant Root->left == P && Root->right == Q || Root->left == Q && Root->right == P.

Anyway, you are only catching the case where P and Q are the children of the same node.  If P and Q are further down the left and right tree then you return nil.
Title: Re: Least Common Ancestor
Post by RamRaul on Feb 13th, 2010, 5:59am

Quote:
You probably meant Root->left == P && Root->right == Q || Root->left == Q && Root->right == P.


no,i meant "||" only and not "&&".


Quote:
Anyway, you are only catching the case where P and Q are the children of the same node.  If P and Q are further down the left and right tree then you return nil.


I ll explian with the help of an algo what i m trying to do...here i m not taking only the case where P and Q are the children of the same node

function LCA (Root, P, Q)
- if Root is NULL return
- if the Root->left is (P or Q) , or the Root->Right is (P or Q)
       then we have the LCA = Root and return it
 else --then no node (P or Q) is found as a direct child of Root) --
     - search for LCA of (P and Q) using the Root->Left as root , call it nleft
     - search for LCA of (P and Q) using the Root->Right as root , call it nright

     if (nleft is LCA AND also nright is LCA -{not NULLS})
         this means that we have one of the nodes (P or Q) on the left OR right of Root(say Right), AND the other node on the Other Side of Root(say left)
     
so the Root "Root" is the LCA for (P, Q) -- because it is impossible that we will find another node after further  "Depth First Search" such that P , Q exists on left and right of it

     else if ONLY nleft is LCA then both (P, Q) are found on the LEFT of Root and nleft is the LCA of them

     else if ONLY nright is LCA then both (P, Q) are found on the Right of Root and nright is the LCA of them
Title: Re: Least Common Ancestor
Post by Grimbal on Feb 14th, 2010, 6:39am
OK, I understand the idea now.

But I don't think it is correct yet.  If you have a node X, P the child of X and Q the child of P, then you return X and not P.
I think the test after root==null should be:
 - If Root is P or Q then return Root.
Title: Re: Least Common Ancestor
Post by RamRaul on Feb 16th, 2010, 9:27am
ya,that condition is needed  for the root to be returned in this case:)
Title: Re: Least Common Ancestor
Post by AB on Mar 15th, 2010, 7:54am
It is more lik this :).. Simplified

Code:
Node LCA(N,n1,n2)
if(N == n1 | N==n2);
return N;
left = LCA(N->left,n1,n2);
if(left != null & left != n1 & left !=n2)
return left;
right = LCA(N->right,n1,n2);
if(right!= null & right!= n1 & right!=n2)
return right;
if(left!=null & right!=null)
return N;
Title: Re: Least Common Ancestor
Post by Hippo on Mar 19th, 2010, 8:40am

on 03/15/10 at 07:54:59, AB wrote:
It is more lik this :).. Simplified

Code:
Node LCA(N,n1,n2)
if(N == n1 | N==n2);
return N;
left = LCA(N->left,n1,n2);
if(left != null & left != n1 & left !=n2)
return left;
right = LCA(N->right,n1,n2);
if(right!= null & right!= n1 & right!=n2)
return right;
if(left!=null & right!=null)
return N;


What does it for N==null? Does it return null anyhow? I don't thing it could work without returning number of "matches" in the subtree.
And when the number equals 2 first time in postorder you are at LCA.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board