@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.