@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 <[email protected]> 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 <[email protected]> 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 > > <[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]> > <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 [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.
