depending upon the situation if you have to find the youngest ancestor
once then what rahul singh can be done
if the situation is you have mutliple query then do it in the following way
preprocessing : make a reversed tree eg
A B C
/ \ => \ /
B C A
so we can go reverse
Know in reversed tree we go from top to bottom from the node making
visited every node comes in path,
doing same for the second node if the node is already visited then that
was the required answer
Complexity: preprocessing O(N)
for searching: length of max path from top to bottom
for balanced tree it will be O(logn)
On 4/8/2010 7:22 PM, Rahul Singh wrote:
Perform inorder traverse for both the node. match element by element
the 2 strings and when first time the string deviates thats Lowest
common ancestor.
-rahul
On Thu, Apr 8, 2010 at 6:21 PM, Anurag Sharma <anuragvic...@gmail.com
<mailto:anuragvic...@gmail.com>> wrote:
@Dave,
Thanks for pointing out the limitation in my algorithm. I myself
realized the same mistake after I posted the algorithm. You are
right, we should additionally check the presence of A and B on the
either side. It will add few extra conditions to the algorithm. I
will soon update the same on my blog.
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Thu, Apr 8, 2010 at 5:32 PM, Dave <dave_and_da...@juno.com
<mailto:dave_and_da...@juno.com>> wrote:
@Anurag.
I like your algorithm, but observe some deficiencies...
A could be on the right subtree and B on the left, as well.
And what if B is a descendent of A. Should we consider A to be the
lowest common ancestor (i.e., is a node an ancestor of
itself?), or is
the LCA the first ancestor of A? In either case, something
more must
be done.
Dave
On Apr 8, 12:34 am, Anurag Sharma <anuragvic...@gmail.com
<mailto:anuragvic...@gmail.com>> wrote:
> Dear Himanshu,
> Here is what I think. This problem can be solved easily by
using recursion.
> Here is the pseudo code for it:
>
> Logic: Let 'A' and 'B' be the given too node whose common
ancestor we have
> to find. Now perform an inorder traversal of the tree and at
every node call
> the 'search(A)' function on the left subtree and search(B)
function on the
> right subtree. When both the results are true, you can be
assured that this
> current node is only the first common ancestor of A, and B,
since below the
> current node, on either tree the other node (A or B) will
not exist, and
> above the current node, both A and B will exist on 1 side,
so again they
> will not exist on either side.
> Heres d pseudo code:
>
> //this is a normal recursive function to search for a Key
node in the tree
> rooted at 'root'
> bool search(node *root, node *key){
>
> if(root==NULL)
> return false;
>
> if(root==key)
> return true;
>
> return search(root->left, key) || search(root->right, key);
>
> }
>
> node* getCommonAncestor(node *root, node *A, node *B){
>
> if(root==NULL)
> return NULL;
>
> //if A is present in the left subtree and B is present in
the right subtree,
> then we have found the common ancestor
> if(search(root->left, A) && search(root->right, B))
> return root;
>
> node* left = getCommonAncestor(root->left, A, B);
> node* right= getCommonAncestor(root->right, A, B);
>
> if(left !=NULL)
> return left;
> if(right !=NULL)
> return right;
>
> return NULL;
>
> }
>
> Hope this helps you.
> Comments welcome
>
> --
> Anurag Sharmahttp://anuragsharma-sun.blogspot.com/
<http://anuragsharma-sun.blogspot.com/>
>
> On Wed, Apr 7, 2010 at 10:04 PM, Himanshu Aggarwal
> <lkml.himan...@gmail.com <mailto:lkml.himan...@gmail.com>>wrote:
>
>
>
> > For a given binary tree, given the root and two node
pointers, how can we
> > find their youngest common ancestor.
>
> > Say the node is like:
>
> > struct node{
> > int data;
> > struct node*left, *right;
> > };
>
> > i.e the father field is not there.
>
> > Please note that it is not a binary search tree, but just
a binary tree.
>
> > Thanks,
> > Himanshu
>
> > --
> > You received this message because you are subscribed to
the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to
algogeeks@googlegroups.com <mailto:algogeeks@googlegroups.com>.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com
<mailto:algogeeks%2bunsubscr...@googlegroups.com><algogeeks%2bunsubscr...@googlegroups.com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.- Hide
quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the
Google Groups "Algorithm Geeks" group.
To post to this group, send email to
algogeeks@googlegroups.com <mailto:algogeeks@googlegroups.com>.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
<mailto:algogeeks%2bunsubscr...@googlegroups.com>.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
<mailto:algogeeks@googlegroups.com>.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
<mailto:algogeeks%2bunsubscr...@googlegroups.com>.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Title:
Tech Team |
Google Groups
