wu :: forums
« wu :: forums - Least Common Ancestor »
Welcome, Guest. Please Login or Register.
Nov 30th, 2024, 9:32pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs (Moderators: Eigenray, Icarus, SMQ, william wu, Grimbal, ThudnBlunder, towr)
   Least Common Ancestor		 « Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Least Common Ancestor  (Read 8194 times)
kanagavel_india
Newbie
*





   


Gender: male
 Posts: 7
Least Common Ancestor  
« on: Feb 14th, 2006, 10:39pm »		 Quote Quote Modify Modify
Hi,
Anybody having a best solution to find Least Common ancestor for two elements in a binary tree.,
 
Regards
Kanagavel A
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: Least Common Ancestor  
« Reply #1 on: Feb 15th, 2006, 12:13am »		 Quote Quote Modify Modify
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)?
IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
kanagavel_india
Newbie
*





   


Gender: male
 Posts: 7
Re: Least Common Ancestor  
« Reply #2 on: Feb 15th, 2006, 1:16am »		 Quote Quote Modify Modify
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
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: Least Common Ancestor  
« Reply #3 on: Feb 15th, 2006, 1:53am »		 Quote Quote Modify Modify
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.
IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
kanagavel_india
Newbie
*





   


Gender: male
 Posts: 7
Re: Least Common Ancestor  
« Reply #4 on: Feb 15th, 2006, 2:19am »		 Quote Quote Modify Modify
Hi towr,
 
Can u explain how to implement ur solution...
 
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: Least Common Ancestor  
« Reply #5 on: Feb 15th, 2006, 3:28am »		 Quote Quote Modify Modify
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.
« Last Edit: Feb 15th, 2006, 4:01am by towr » IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
kanagavel_india
Newbie
*





   


Gender: male
 Posts: 7
Re: Least Common Ancestor  
« Reply #6 on: Feb 15th, 2006, 3:40am »		 Quote Quote Modify Modify
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
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: Least Common Ancestor  
« Reply #7 on: Feb 15th, 2006, 4:10am »		 Quote Quote Modify Modify
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.
IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
shallow
Newbie
*





   


Posts: 2
Re: Least Common Ancestor  
« Reply #8 on: Apr 25th, 2006, 6:52am »		 Quote Quote Modify Modify
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.
IP Logged
KWillets
Junior Member
**





   


Posts: 84
Re: Least Common Ancestor  
« Reply #9 on: May 1st, 2006, 11:13am »		 Quote Quote Modify Modify
This is a well-know problem, but I can summarize.
 
hidden:

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/lectur e11.pdf  
IP Logged
Ved
Junior Member
**





   


Gender: male
 Posts: 53
Re: Least Common Ancestor  
« Reply #10 on: Jan 22nd, 2010, 10:47pm »		 Quote Quote Modify Modify
on May 1st, 2006, 11:13am, KWillets wrote:
This is a well-know problem, but I can summarize.
 
hidden:

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/lectur e11.pdf  

 
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.  Shocked
« Last Edit: Jan 22nd, 2010, 10:53pm by Ved » IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
 Posts: 7527
Re: Least Common Ancestor  
« Reply #11 on: Jan 23rd, 2010, 8:00am »		 Quote Quote Modify Modify
@Ved: that is in other words what towr proposed.  It should work.
IP Logged
bmudiam
Junior Member
**





   


Gender: male
 Posts: 55
Re: Least Common Ancestor  
« Reply #12 on: Jan 23rd, 2010, 11:22am »		 Quote Quote Modify Modify
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.
« Last Edit: Jan 23rd, 2010, 11:23am by bmudiam » IP Logged
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
Aryabhatta
Uberpuzzler
*****






   


Gender: male
 Posts: 1321
Re: Least Common Ancestor  
« Reply #13 on: Jan 23rd, 2010, 2:10pm »		 Quote Quote Modify Modify
on Jan 23rd, 2010, 11:22am, 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.
« Last Edit: Jan 23rd, 2010, 2:10pm by Aryabhatta » IP Logged
Ved
Junior Member
**





   


Gender: male
 Posts: 53
Re: Least Common Ancestor  
« Reply #14 on: Jan 24th, 2010, 2:00am »		 Quote Quote Modify Modify
on Jan 23rd, 2010, 8:00am, 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.  
IP Logged
R
Senior Riddler
****



Addicted!!!

   


Gender: male
 Posts: 502
Re: Least Common Ancestor  
« Reply #15 on: Jan 24th, 2010, 1:18pm »		 Quote Quote Modify Modify
on Feb 15th, 2006, 3:40am, 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.
IP Logged
The first experience seems like Magic, but the second tells you the Trick behind it.
serenity
Newbie
*





   


Posts: 25
Re: Least Common Ancestor  
« Reply #16 on: Feb 12th, 2010, 2:11am »		 Quote Quote Modify Modify
it is least common or lowest common ancestor ??  Roll Eyes
IP Logged
RamRaul
Newbie
*





  rahul7132003  


Gender: male
 Posts: 5
Re: Least Common Ancestor  
« Reply #17 on: Feb 12th, 2010, 9:08am »		 Quote Quote Modify Modify
I hv come out with a simpler code...hope this works Cool
 
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;
}
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
 Posts: 7527
Re: Least Common Ancestor  
« Reply #18 on: Feb 12th, 2010, 10:01am »		 Quote Quote Modify Modify
on Feb 12th, 2010, 9:08am, RamRaul wrote:
...hope this works Cool

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.
IP Logged
RamRaul
Newbie
*





  rahul7132003  


Gender: male
 Posts: 5
Re: Least Common Ancestor  
« Reply #19 on: Feb 13th, 2010, 5:59am »		 Quote Quote Modify Modify
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
 
 
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
 Posts: 7527
Re: Least Common Ancestor  
« Reply #20 on: Feb 14th, 2010, 6:39am »		 Quote Quote Modify Modify
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.
IP Logged
RamRaul
Newbie
*





  rahul7132003  


Gender: male
 Posts: 5
Re: Least Common Ancestor  
« Reply #21 on: Feb 16th, 2010, 9:27am »		 Quote Quote Modify Modify
ya,that condition is needed  for the root to be returned in this caseSmiley
IP Logged
AB
Newbie
*





   


Posts: 20
Re: Least Common Ancestor  
« Reply #22 on: Mar 15th, 2010, 7:54am »		 Quote Quote Modify Modify
It is more lik this Smiley.. 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;
IP Logged
Hippo
Uberpuzzler
*****





   


Gender: male
 Posts: 919
Re: Least Common Ancestor  
« Reply #23 on: Mar 19th, 2010, 8:40am »		 Quote Quote Modify Modify
on Mar 15th, 2010, 7:54am, AB wrote:
It is more lik this Smiley.. 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.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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