DON's solution will work
On Sep 3, 11:28 am, Abhishek Yadav <algowithabhis...@gmail.com> wrote:
> 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 <
>
>
>
>
>
>
>
> bagana.bharatku...@gmail.com> 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 <rajuljain...@gmail.com>wrote:
>
> >> @anika this solution only works for BST
>
> >> On Mon, Aug 15, 2011 at 4:20 PM, Anika Jain <anika.jai...@gmail.com>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 <yasir....@gmail.com> 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 algogeeks@googlegroups.com.
> >>>> To unsubscribe from this group, send email to
> >>>> algogeeks+unsubscr...@googlegroups.com.
> >>>> 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 algogeeks@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com.
> >>> 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 algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> 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*
> > <bagana.bharatku...@gmail.com>
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
