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 Sharma
http://anuragsharma-sun.blogspot.com/
On Wed, Apr 7, 2010 at 10:04 PM, Himanshu Aggarwal
<[email protected]>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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
