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