@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%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com> >> > >> > > <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com> >> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@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%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@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<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.
