@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>
> > .
> > 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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
