@Ritu - Do you realize that you cannot just convert a given binary tree into right-threaded binary tree? You need at least 1 bit information at each node to specify whether the right pointer of that node is a regular pointer or pointer to the inorder successor. This is because traversal is done differently when you arrive at a node through its inorder predecessor.
On Thu, Jan 27, 2011 at 7:22 AM, Ritu Garg <[email protected]> wrote: > solution is not too hard to understand!! > 1. [quote] For every none leaf node , go to the last node in it's left > > subtree and mark the right child of that node as x [\quote]. How are > we going to refer to the right child now ??We have removed it's > reference now !! > > last node in left sub tree of any node always have right pointer as NULL > because this is the last node > > 2. It is to be repeated for every node except the non leaf nodes . This > > will take O(n*n) time in worst case , say a leftist tree with only > left pointers . root makes n-1 traversals , root's left subtree's root > makes n-2 , and so on. > i said that it ll take O(n) time for well balanced tree. > for a node at height h ,it takes O(h) to fill this node as successor of > some other node.if combined for all sum(O(h)) h=1 to lg n ..total time ll > come as O(n) > > 3. Take the case below . > > > 1 > 2 3 > 1 1.5 2.5 4 > > for node 2 , you will go to 1 , which is the successor of 2 , you make > 2->right=1 .... but what about node 1.5 ??? > same is the case with node 3 ... 3->right=2.5 . How will we refer to 4 > now ?? > > when you ll process node 1,it ll be filled in as right child of 1.5 > there is no successor for 4. > > In Brief > > 1. Convert the tree to right threaded binary tree.means all right children > point to their successors. > it ll take no additional space.ll take O(n) time if tree is well balanced > > 2. Do inorder traversal to find ith element without using extra space > because succssor of each node is pointed by right child. > > i hope you got it now!! > > > > > > > > On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava < > [email protected]> wrote: > >> I don't seem to understand ur solution . >> [quote] For every none leaf node , go to the last node in it's left >> subtree and mark the right child of that node as x [\quote]. How are >> we going to refer to the right child now ??We have removed it's >> reference now !! >> >> It is to be repeated for every node except the non leaf nodes . This >> will take O(n*n) time in worst case , say a leftist tree with only >> left pointers . root makes n-1 traversals , root's left subtree's root >> makes n-2 , and so on. >> >> Go to the largest node in the left subtree .This means go to the left >> subtree and keep on going to the right until it becomes null , in >> which case , you make y->right as x . This means effectively , that y >> is the predecessor of x , in the tree . Considering a very good code , >> it may take O(1) space , but you will still need additional pointers. >> Take the case below . >> >> 1 >> 2 3 >> 1 1.5 2.5 4 >> >> for node 2 , you will go to 1 , which is the successor of 2 , you make >> 2->right=1 .... but what about node 1.5 ??? >> same is the case with node 3 ... 3->right=2.5 . How will we refer to 4 >> now ?? >> >> Now using inorder traversal with a count , I will start at 1->left , 2- >> >left = 1 , then 2 ... then 2->right = 1 again . then 1 , and then 1- >> >right=3 ...clearly , this will not give us a solution . >> A reverse inorder looks just fine to me . >> >> On Jan 26, 3:14 pm, Ritu Garg <[email protected]> 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 <[email protected]> >> 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 <[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%2Bunsubscribe@googlegroups .com> >> > >> <algogeeks%[email protected]<algogeeks%[email protected]> >> <algogeeks%252Bunsubscribe@googleg roups.com> >> > >> > >> > > <algogeeks%[email protected]<algogeeks%[email protected]> >> <algogeeks%252Bunsubscribe@googleg roups.com> >> > >> <algogeeks%[email protected]<algogeeks%[email protected]> >> <algogeeks%25252Bunsubscribe@goo glegroups.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 [email protected]. >> > >> > > To unsubscribe from this group, send email to >> > >> > > [email protected]<algogeeks%[email protected]> >> <algogeeks%2Bunsubscribe@googlegroups .com> >> > >> <algogeeks%[email protected]<algogeeks%[email protected]> >> <algogeeks%252Bunsubscribe@googleg roups.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 [email protected]. >> > >> To unsubscribe from this group, send email to >> > >> [email protected]<algogeeks%[email protected]> >> <algogeeks%2Bunsubscribe@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 [email protected]. >> > > To unsubscribe from this group, send email to >> > > [email protected]<algogeeks%[email protected]> >> <algogeeks%2Bunsubscribe@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 [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]<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.
