I know this is not a BST , in BST you do not have to inorder traversal it is even shorter. You start from root and first instance when node1 < currentNode < node 2 (or vice versa)you are done .
In case of normal binary tree. you just need to traverse till node1 and then similarly for node2 . Now you have 2 paths, first deviation of path is ur youngest ancestor -rahul On Thu, Apr 8, 2010 at 9:11 PM, Anurag Sharma <[email protected]>wrote: > @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]<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.
