@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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[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]> > <algogeeks%[email protected]<algogeeks%[email protected]> > > > > > <algogeeks%[email protected]<algogeeks%[email protected]> > <algogeeks%[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]<algogeeks%[email protected]> > <algogeeks%[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]<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.
