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 <[email protected]> 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++ <[email protected]> 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 [email protected].
> > To unsubscribe from this group, send email to
> > [email protected]<algogeeks%[email protected]>
> > .
> > 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
