@Rahul, The Tree is not Binary "Search" Tree. Anurag Sharma http://anuragsharma-sun.blogspot.com/
On Thu, Apr 8, 2010 at 6:52 PM, Rahul Singh <[email protected]> wrote: > 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]<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.
