it can done in with 2 stack(size/length of the each stack is hieght of the
tree),(stack1,stack2)
//find the first element using in order
{
stack1[num_stack1++]=(pushing the ancestor of the first element) in first
stack.
}
//find the second element using in order
stack2[num_stack2++]= (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.
Thank you,
Sid.
On Sat, Sep 3, 2011 at 7:25 PM, siddharam suresh <siddharam....@gmail.com>wrote:
> 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.
