this solution works if parent pointer is given. 1. Start moving up from both the nodes (if two nodes become equal, fine this is the common ancestor) till you reach the root node and in between count the number of nodes you covered in their path for both the nodes. Say 7 for node A and 10 for node B. 2. Now from B (longer path node) move up 3 (10-7) nodes. 3. now start moving up from B's new position and from A. Wherever they meet is the common ancestor.
On Sat, Sep 3, 2011 at 11:13 AM, bharatkumar bagana < [email protected]> wrote: > For BST it is easy ...it can be find in O(logn) time .. > when ever we find that the direction we are searching for x and y are > different, that node is the common ancestor ...no need to find either x or y > where the nodes are... > what about binary tree ? how do we search an element in binary tree > efficiently ? > > > On Sat, Sep 3, 2011 at 12:44 AM, rajul jain <[email protected]>wrote: > >> @anika this solution only works for BST >> >> On Mon, Aug 15, 2011 at 4:20 PM, Anika Jain <[email protected]>wrote: >> >>> node *common_ancestor(node *root, node **prev, int x,int y) >>> { >>> if(root->a==x || root->a==y) >>> return *prev; >>> else if(root->a > x && root->a > y) >>> { >>> prev=&root; >>> return common_ancestor(root->l,prev, x,y); >>> } >>> else if(root->a < x && root->a < y) >>> { >>> prev=&root; >>> return common_ancestor(root->r,prev, x,y); >>> } >>> else >>> { >>> prev=&root; >>> return *prev; >>> } >>> } >>> >>> with call as >>> node *prev=NULL; >>> common_ancestor(root,&prev,x,y); >>> >>> >>> On Sun, Aug 14, 2011 at 10:08 PM, Yasir <[email protected]> wrote: >>> >>>> Guys, How about the below mentioned implementation? >>>> The only assumptions is that nodes should exist in the tree. (will fail >>>> if one node exists and another doesn't) >>>> >>>> static Node LCA(Node root, int d1, int d2){ >>>> if(root==null) >>>> return root; >>>> if(root.left!=null && ( root.left.data == d1 || root.left.data==d2 ) ) >>>> // both nodes exists in left sub-tree >>>> return root; >>>> >>>> if(root.right!=null && ( root.right.data == d1 || root.right.data==d2) ) >>>> // both nodes exists in right sub-tree >>>> return root; >>>> Node ltree = LCA(root.left, d1, d2); //check recursively in left >>>> subtree >>>> Node rtree = LCA(root.right, d1, d2); // check recursively in >>>> right subtree >>>> if(ltree!=null && rtree!=null) // One node in left & another in >>>> right >>>> return root; >>>> return (ltree==null)?rtree:ltree; >>>> } >>>> >>>> >>>> Just to mention that, closest ancestor of 5&4 OR 4&9 would be 3 in the >>>> following tree: >>>> 3 >>>> \ >>>> 4 >>>> / \ >>>> 5 8 >>>> / >>>> 9 >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To view this discussion on the web visit >>>> https://groups.google.com/d/msg/algogeeks/-/24JUUQsBHvIJ. >>>> >>>> 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. >>>> >>> >>> -- >>> 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. >>> >> >> -- >> 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. >> > > > > -- > > **Please do not print this e-mail until urgent requirement. Go Green!! > Save Papers <=> Save Trees > *BharatKumar Bagana* > **http://www.google.com/profiles/bagana.bharatkumar<http://www.google.com/profiles/bagana.bharatkumar> > * > Mobile +91 8056127652* > <[email protected]> > > > -- > 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. > -- 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.
