This will works well to find common ancestor
mynode *closestAncestor(mynode* root, mynode* p, mynode* q)
{
mynode *l, *r, *tmp;
if(root == NULL)
{
return(NULL);
}
if(root->left==p || root->right==p || root->left==q || root->right==q)
{
return(root);
}
else
{
l = closestAncestor(root->left, p, q);
r = closestAncestor(root->right, p, q);
if(l!=NULL && r!=NULL)
{
return(root);
}
else
{
tmp = (l!=NULL) ? l : r;
return(tmp);
}
}
}
----------------------------------------
CHERUVU JAANU REDDY
M.Tech in CSIS
On Thu, Apr 8, 2010 at 7:22 PM, Rahul Singh <rahu...@gmail.com> 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>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> 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> 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/
>>> >
>>> > On Wed, Apr 7, 2010 at 10:04 PM, Himanshu Aggarwal
>>> > <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 algoge...@googlegroups.com.
>>> > > To unsubscribe from this group, send email to
>>> > > algogeeks+unsubscr...@googlegroups.com<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 algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com<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<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<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.
