it can done in with 2 stack(size/length of the each stack is hieght of the
tree),(stack1,stack2)
num_stack1=find the first element using in order (pushing the ancestor of
the first element) in first stack.
num_stack2=find the second element using in order (pushing the ancestor of
the second element) in second stack.
num_stack1=num_stack2=num_stack1<num_stack2?num_stack1:num_stack2;
while(stack1[num_stack1--]!=stack2[num_stack2--]);
return (stack1[num_stack1])
Thank you,
Sid.
On Sat, Sep 3, 2011 at 6:05 PM, vikas <vikas.rastogi2...@gmail.com> wrote:
> 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.
>
>
--
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.
