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> > > . > > 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.