@Ritu, Right ! I misread you post On Wed, Jan 26, 2011 at 3:44 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%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<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.
