Re: [algogeeks] Build BST from binary tree without extra space
thing is that u r using recursion and we don't have to use it( recussion use memory indirectly) as per the question On Thu, Apr 29, 2010 at 3:55 PM, Algoose Chase harishp...@gmail.com wrote: If you mean to convert the binary tree to binary search tree directly , then BinarytoBST(Node* root) { if( root == nulll) return; BinarytoBST(root-left); BinarytoBST(root-right); if( root-left ) Node* NodeL = MAX(root-left); if ( root-right ) Node* NodeR = MIN(root-right); if( NodeL-Data root-data) { // swap values. temp = NodeL-data; NodeL-data = root-data; root-data = temp; BinarytoBST(NodeL); } if( NodeR-Data = root-data) { // swap values. temp = NodeR-data; NodeR-data = root-data; root-data = temp; BinarytoBST(NodeR); } On Thu, Apr 29, 2010 at 11:23 AM, Algoose Chase harishp...@gmail.com wrote: Hi, How do you define without extra space ? Doing any order traversal either using recursion or using iteration is going to take extra space . If you are given a binary tree represented by pointers that points to children nodes is it possible to do a heap sort without an array ? On Thu, Apr 29, 2010 at 6:59 AM, sharad kumar aryansmit3...@gmail.com wrote: my choice is build a min heap .sort the array with heap sort.then find the median of the sorted array and build tree On Wed, Apr 28, 2010 at 10:16 PM, Vivek S s.vivek.ra...@gmail.com wrote: @Rajesh Patidar I think we should do in Post order traversal alone. If we go by Preorder/Inorder we might lose track of children node that is currently being inserted into the BST. - correct me if im wrong :) On 28 April 2010 15:30, Rajesh Patidar patidarc...@gmail.com wrote: pickup node in any order no matter(pre,post,inorder) and just one by one. start adding the node into bst no need to use extra space u have to just ditach the node from binary tree and attach it in bst. On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra amishra@gmail.com wrote: How to build BST from binary tree in place i.e without 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 algoge...@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. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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. -- Reduce, Reuse and Recycle Regards, Vivek.S -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Build BST from binary tree without extra space
Hi, How do you define without extra space ? Doing any order traversal either using recursion or using iteration is going to take extra space . If you are given a binary tree represented by pointers that points to children nodes is it possible to do a heap sort without an array ? On Thu, Apr 29, 2010 at 6:59 AM, sharad kumar aryansmit3...@gmail.comwrote: my choice is build a min heap .sort the array with heap sort.then find the median of the sorted array and build tree On Wed, Apr 28, 2010 at 10:16 PM, Vivek S s.vivek.ra...@gmail.com wrote: @Rajesh Patidar I think we should do in Post order traversal alone. If we go by Preorder/Inorder we might lose track of children node that is currently being inserted into the BST. - correct me if im wrong :) On 28 April 2010 15:30, Rajesh Patidar patidarc...@gmail.com wrote: pickup node in any order no matter(pre,post,inorder) and just one by one. start adding the node into bst no need to use extra space u have to just ditach the node from binary tree and attach it in bst. On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra amishra@gmail.com wrote: How to build BST from binary tree in place i.e without 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Reduce, Reuse and Recycle Regards, Vivek.S -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%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 algoge...@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.
Re: [algogeeks] Build BST from binary tree without extra space
ya post order traversal will not have these problem theme time i haven't thought the problem with pre and inorder. On Wed, Apr 28, 2010 at 10:16 PM, Vivek S s.vivek.ra...@gmail.com wrote: @Rajesh Patidar I think we should do in Post order traversal alone. If we go by Preorder/Inorder we might lose track of children node that is currently being inserted into the BST. - correct me if im wrong :) On 28 April 2010 15:30, Rajesh Patidar patidarc...@gmail.com wrote: pickup node in any order no matter(pre,post,inorder) and just one by one. start adding the node into bst no need to use extra space u have to just ditach the node from binary tree and attach it in bst. On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra amishra@gmail.com wrote: How to build BST from binary tree in place i.e without 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 algoge...@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. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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. -- Reduce, Reuse and Recycle Regards, Vivek.S -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Build BST from binary tree without extra space
If you mean to convert the binary tree to binary search tree directly , then BinarytoBST(Node* root) { if( root == nulll) return; BinarytoBST(root-left); BinarytoBST(root-right); if( root-left ) Node* NodeL = MAX(root-left); if ( root-right ) Node* NodeR = MIN(root-right); if( NodeL-Data root-data) { // swap values. temp = NodeL-data; NodeL-data = root-data; root-data = temp; BinarytoBST(NodeL); } if( NodeR-Data = root-data) { // swap values. temp = NodeR-data; NodeR-data = root-data; root-data = temp; BinarytoBST(NodeR); } On Thu, Apr 29, 2010 at 11:23 AM, Algoose Chase harishp...@gmail.comwrote: Hi, How do you define without extra space ? Doing any order traversal either using recursion or using iteration is going to take extra space . If you are given a binary tree represented by pointers that points to children nodes is it possible to do a heap sort without an array ? On Thu, Apr 29, 2010 at 6:59 AM, sharad kumar aryansmit3...@gmail.comwrote: my choice is build a min heap .sort the array with heap sort.then find the median of the sorted array and build tree On Wed, Apr 28, 2010 at 10:16 PM, Vivek S s.vivek.ra...@gmail.comwrote: @Rajesh Patidar I think we should do in Post order traversal alone. If we go by Preorder/Inorder we might lose track of children node that is currently being inserted into the BST. - correct me if im wrong :) On 28 April 2010 15:30, Rajesh Patidar patidarc...@gmail.com wrote: pickup node in any order no matter(pre,post,inorder) and just one by one. start adding the node into bst no need to use extra space u have to just ditach the node from binary tree and attach it in bst. On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra amishra@gmail.com wrote: How to build BST from binary tree in place i.e without 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Reduce, Reuse and Recycle Regards, Vivek.S -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%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 algoge...@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.
Re: [algogeeks] Build BST from binary tree without extra space
@ashish i forgot recussion uses memory but if we have to do it without using stack also then pickup the root and add it to the bst and to fill the vacant position of root choose left node and make it root and to adjust previous right node at it to leaf eg : D / \ A E / \ B C add D to the BST and add E to the leaf A / \ B C / E adding E to the leaf node can be done memory without using extra memory. On Wed, Apr 28, 2010 at 8:22 PM, Ashish Mishra amishra@gmail.com wrote: @rajesh can u explain your soln how u r doing inorder, pre or whatever (without using stack) and at same time build BST On Wed, Apr 28, 2010 at 3:30 PM, Rajesh Patidar patidarc...@gmail.com wrote: pickup node in any order no matter(pre,post,inorder) and just one by one. start adding the node into bst no need to use extra space u have to just ditach the node from binary tree and attach it in bst. On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra amishra@gmail.com wrote: How to build BST from binary tree in place i.e without 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 algoge...@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. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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. -- Ashish Mishra http://ashishmishra.weebly.com/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Build BST from binary tree without extra space
On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra amishra@gmail.comwrote: How to build BST from binary tree in place i.e without extra space ?? Are you looking for: http://discuss.joelonsoftware.com/default.asp?interview.11.781167.4 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Junior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Build BST from binary tree without extra space
pickup node in any order no matter(pre,post,inorder) and just one by one. start adding the node into bst no need to use extra space u have to just ditach the node from binary tree and attach it in bst. On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra amishra@gmail.com wrote: How to build BST from binary tree in place i.e without 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 algoge...@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. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Build BST from binary tree without extra space
@ Rajesh: there may be a problem with this solution. Suppose I start detaching the nodes from the binary tree in the following order - Root, Left, Right. So as soon as i detach the root of the binary tree and form a new BST with it ( on which i m going to make further node additions), I am left with 2 sub trees ( the left subtree the right one). So i must have a way to manage them. We'll have to use a queue for that but this will lead to extra space utilization. On Wed, Apr 28, 2010 at 3:30 PM, Rajesh Patidar patidarc...@gmail.comwrote: pickup node in any order no matter(pre,post,inorder) and just one by one. start adding the node into bst no need to use extra space u have to just ditach the node from binary tree and attach it in bst. On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra amishra@gmail.com wrote: How to build BST from binary tree in place i.e without 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%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 algoge...@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.
Re: [algogeeks] Build BST from binary tree without extra space
@rajesh can u explain your soln how u r doing inorder, pre or whatever (without using stack) and at same time build BST On Wed, Apr 28, 2010 at 3:30 PM, Rajesh Patidar patidarc...@gmail.comwrote: pickup node in any order no matter(pre,post,inorder) and just one by one. start adding the node into bst no need to use extra space u have to just ditach the node from binary tree and attach it in bst. On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra amishra@gmail.com wrote: How to build BST from binary tree in place i.e without 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Ashish Mishra http://ashishmishra.weebly.com/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Build BST from binary tree without extra space
@Rajesh Patidar I think we should do in Post order traversal alone. If we go by Preorder/Inorder we might lose track of children node that is currently being inserted into the BST. - correct me if im wrong :) On 28 April 2010 15:30, Rajesh Patidar patidarc...@gmail.com wrote: pickup node in any order no matter(pre,post,inorder) and just one by one. start adding the node into bst no need to use extra space u have to just ditach the node from binary tree and attach it in bst. On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra amishra@gmail.com wrote: How to build BST from binary tree in place i.e without 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Reduce, Reuse and Recycle Regards, Vivek.S -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Build BST from binary tree without extra space
my choice is build a min heap .sort the array with heap sort.then find the median of the sorted array and build tree On Wed, Apr 28, 2010 at 10:16 PM, Vivek S s.vivek.ra...@gmail.com wrote: @Rajesh Patidar I think we should do in Post order traversal alone. If we go by Preorder/Inorder we might lose track of children node that is currently being inserted into the BST. - correct me if im wrong :) On 28 April 2010 15:30, Rajesh Patidar patidarc...@gmail.com wrote: pickup node in any order no matter(pre,post,inorder) and just one by one. start adding the node into bst no need to use extra space u have to just ditach the node from binary tree and attach it in bst. On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra amishra@gmail.com wrote: How to build BST from binary tree in place i.e without 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Reduce, Reuse and Recycle Regards, Vivek.S -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.