@Priyanka - what exactly is the difference between extra space and auxiliary
space? As far as the algorithm is concerned, it does use space whose order
of growth is a function of the input size and that is all that matters here.
On Wed, Jan 26, 2011 at 7:55 AM, may.I.answer <may.i.answ...@gmail.com>wrote:
> Well the solution is pretty simple.
> What you have to do is just do inoder traversal of tree in reverse
> order.
>
> Here goes my C++ code for that
> int ith_order(Tree *root,int i)
> {
> static int c;
> static int ans;
> if(root)
> {
> ith_order(root->right,i);
> ++c;
> if(c==i)
> return ans=root->data;
>
> ith_order(root->left,i);
>
> }
> return ans;
> }
>
> please correct me if i am wrong :)
> On Jan 26, 5:01 pm, sankalp srivastava <richi.sankalp1...@gmail.com>
> wrote:
> > I don't seem to understand ur solution .
> > [quote] For every none leaf node , go to the last node in it's left
> > subtree and mark the right child of that node as x [\quote]. How are
> > we going to refer to the right child now ??We have removed it's
> > reference now !!
> >
> > It is to be repeated for every node except the non leaf nodes . This
> > will take O(n*n) time in worst case , say a leftist tree with only
> > left pointers . root makes n-1 traversals , root's left subtree's root
> > makes n-2 , and so on.
> >
> > Go to the largest node in the left subtree .This means go to the left
> > subtree and keep on going to the right until it becomes null , in
> > which case , you make y->right as x . This means effectively , that y
> > is the predecessor of x , in the tree . Considering a very good code ,
> > it may take O(1) space , but you will still need additional pointers.
> > Take the case below .
> >
> > 1
> > 2 3
> > 1 1.5 2.5 4
> >
> > for node 2 , you will go to 1 , which is the successor of 2 , you make
> > 2->right=1 .... but what about node 1.5 ???
> > same is the case with node 3 ... 3->right=2.5 . How will we refer to 4
> > now ??
> >
> > Now using inorder traversal with a count , I will start at 1->left ,
> 2->left = 1 , then 2 ... then 2->right = 1 again . then 1 , and then 1-
> > >right=3 ...clearly , this will not give us a solution .
> >
> > A reverse inorder looks just fine to me .
> >
> > On Jan 26, 3:14 pm, Ritu Garg <ritugarg.c...@gmail.com> wrote:
> >
> >
> >
> >
> >
> >
> >
> > > @Algoose
> >
> > > I said ..*.For every node x,go to the last node in its left subtree and
> mark
> > > the right child of that node as x.*
> >
> > > it is to be repeated for all nodes except leaf nodes.
> > > to apply this approach ,you need to go down the tree.No parent pointers
> > > required.
> > > for every node say x whose left sub tree is not null ,go to the largest
> node
> > > in left sub-tree say y.
> > > Set y->right = x
> > > y is the last node to be processed in left sub-tree of x hence x is
> > > successor of y.
> >
> > > On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase <harishp...@gmail.com>
> wrote:
> > > > @ritu
> > > > how would you find a successor without extra space if you dont have a
> > > > parent pointer ?
> > > > for Instance from the right most node of left subtree to the parent
> of left
> > > > subtree(root) ?
> > > > @Juver++
> > > > Internal stack does count as extra space !!
> >
> > > > On Wed, Jan 26, 2011 at 3:02 PM, ritu <ritugarg.c...@gmail.com>
> wrote:
> >
> > > >> No,no extra space is needed.
> > > >> Right children which are NULL pointers are replaced with pointer to
> > > >> successor.
> >
> > > >> On Jan 26, 1:18 pm, nphard nphard <nphard.nph...@gmail.com> wrote:
> > > >> > If you convert the given binary tree into right threaded binary
> tree,
> > > >> won't
> > > >> > you be using extra space while doing so? Either the given tree
> should
> > > >> > already be right-threaded (or with parent pointers at each node)
> or
> > > >> internal
> > > >> > stack should be allowed for recursion but no extra space usage
> apart
> > > >> from
> > > >> > that.
> >
> > > >> > On Wed, Jan 26, 2011 at 3:04 AM, ritu <ritugarg.c...@gmail.com>
> wrote:
> > > >> > > it can be done in O(n) time using right threaded binary tree.
> > > >> > > 1.Convert the tree to right threaded tree.
> > > >> > > right threaded tree means every node points to its successor in
> > > >> > > tree.if right child is not NULL,then it already contains a
> pointer to
> > > >> > > its successor Else it needs to filled up as following
> > > >> > > a. For every node x,go to the last node in its left subtree
> and
> > > >> > > mark the right child of that node as x.
> > > >> > > It Can be done in O(n) time if tree is a balanced tree.
> >
> > > >> > > 2. Now,Traverse the tree with Inorder Traversal without using
> > > >> > > additional space(as successor of any node is available O(1)
> time) and
> > > >> > > keep track of 5th largest element.
> >
> > > >> > > Regards,
> > > >> > > Ritu
> >
> > > >> > > On Jan 26, 8:38 am, nphard nphard <nphard.nph...@gmail.com>
> wrote:
> > > >> > > > Theoretically, the internal stack used by recursive functions
> must
> > > >> be
> > > >> > > > considered for space complexity.
> >
> > > >> > > > On Mon, Jan 24, 2011 at 5:40 AM, juver++ <
> avpostni...@gmail.com>
> > > >> wrote:
> > > >> > > > > internal stack != extra space
> >
> > > >> > > > > --
> > > >> > > > > 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<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2Bunsubscribe@googlegroups .com>
> > > >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> <algogeeks%252Bunsubscribe@googleg roups.com>
> >
> > > >> > > <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> <algogeeks%252Bunsubscribe@googleg roups.com>
> > > >> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@googlegroups.com>
> <algogeeks%25252Bunsubscribe@goo glegroups.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<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2Bunsubscribe@googlegroups .com>
> > > >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> <algogeeks%252Bunsubscribe@googleg roups.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<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2Bunsubscribe@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<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2Bunsubscribe@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<algogeeks%2bunsubscr...@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.
