Re: [algogeeks] Re: Merge two BST in O(n) time with O(1)
With only these 2 constraints you can just insert the root of smaller tree into bigger one and using rotations bring it to leaf. Now attach the left and right subtrees to the inserted node. Expected O(log n) Worst O(n) Space O(1) -Rohit On Mon, Mar 8, 2010 at 5:14 AM, lalit gera lalitger...@gmail.com wrote: new tree will be a right skewed tree.. any other idea?? On Jan 29, 6:55 am, ShingRay masterrays...@gmail.com wrote: Oh, I have said something wrong. 1. Inorder traverse both trees. This gives two sorted list. È(m+n) 2. Merge the two sorted list A, B into a new one C. È(m+n) 3. Build a new tree using C. Each node of the tree has just one child. È(m+n) -- 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.
[algogeeks] Re: Merge two BST in O(n) time with O(1)
We dont have to do anything more for BST2 as all children of BST2 are already at their proper place how can we insert BST2 into BST1 only checking the root value?? say BST1's root value is 25 and BST2's root value is 35, then BST2 will be inserted in right to BST1's root. If BST2 has minimum value 1 (leftmost child), BST1 has minimum 2, then it violates the BST conditions. or even left child of BST2 is 24 it again violates the condition :P On Jan 29, 5:10 am, Ashish Meena ashishmee...@gmail.com wrote: Hi all, Lets say we do following steps to merge two BSTS's. Lets call them BST1 and BST2. 1. Check the value of root of BST2. 2. In BST1 find a place where root of BST2 can be put. 3. Remove the children from this place and store them as BST3 and BST4. 3. Attach BST2's root pointer at this place. We dont have to do anything more for BST2 as all children of BST2 are already at their proper place Now our BST1 has BST2 merged to it but it doesnt have BST3 and BST4. 4. Do inorder traversal of BST3 and BST4 and insert it to BST1. If we know the approximate size of BST1 and BST2 we can choose tree for our step 1 accordingly. This algorithm doesnt need any extra memory and can be almost O(n), if BST3 and BST4 are very small trees. Does anybody see any issues with this approach? Regards, Ashish On Fri, Jan 29, 2010 at 2:52 PM, vivek bijlwan viv...@gmail.com wrote: @ shingray ... cartesian trees are not BSTs . I guess nirmal's question asks for a BST. also cartesian trees have extra space requirements. On Fri, Jan 29, 2010 at 12:07 AM, naga vinod kumar vinodkumark...@gmail.com wrote: hi varun ,it cant be in O(n) time ,it can be merged in O(nlogn) time. On Thu, Jan 28, 2010 at 10:37 PM, Varun S V varun...@gmail.com wrote: Delete the nodes in the second BST in postorder. As and when you delete this node, insert it into the first BST. On Thu, Jan 28, 2010 at 9:35 PM, Bijlwan viv...@gmail.com wrote: hey nirmal . i don't get that when you merge the two linked list , how do you get the BST? making the BST would itself be a O(nlogn) process? On Jan 28, 5:03 am, Nirmal nirm...@gmail.com wrote: Given two binary search trees, how to merge them in O(n) time and O(1) space? It can be done using O(n) space as below, 1. covert BST #1 into linked list or sorted array 2. covert BST #2 into linked list or sorted array 3. merge them... but how to do this in place? -- 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.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.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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Ashish Meena -- 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.
[algogeeks] Re: Merge two BST in O(n) time with O(1)
new tree will be a right skewed tree.. any other idea?? On Jan 29, 6:55 am, ShingRay masterrays...@gmail.com wrote: Oh, I have said something wrong. 1. Inorder traverse both trees. This gives two sorted list. È(m+n) 2. Merge the two sorted list A, B into a new one C. È(m+n) 3. Build a new tree using C. Each node of the tree has just one child. È(m+n) -- 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.
[algogeeks] Re: Merge two BST in O(n) time with O(1)
@Varun S V Appending the nodes to the first subtree will result in O(mlgn) as each node of second BST will have to go through log n level of the first BST On Jan 29, 12:37 am, Varun S V varun...@gmail.com wrote: Delete the nodes in the second BST in postorder. As and when you delete this node, insert it into the first BST. On Thu, Jan 28, 2010 at 9:35 PM, Bijlwan viv...@gmail.com wrote: hey nirmal . i don't get that when you merge the two linked list , how do you get the BST? making the BST would itself be a O(nlogn) process? On Jan 28, 5:03 am, Nirmal nirm...@gmail.com wrote: Given two binary search trees, how to merge them in O(n) time and O(1) space? It can be done using O(n) space as below, 1. covert BST #1 into linked list or sorted array 2. covert BST #2 into linked list or sorted array 3. merge them... but how to do this in place? -- 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.- Hide quoted text - - Show quoted text - -- 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] Re: Merge two BST in O(n) time with O(1)
Hi, @Asish meena and Arun : I dont think you can simply append a whole tree( BST2) at some position just because the root of the BST2 is at its correct position.For instance , Lets say you append BST2's Root anywhere within the left subtree of BST1's Root. But if the right most leaf node of BST2 is greater than the root of BST1, then the merged tree is no longer a binary search tree. Hence your approach will not work in all cases. On Wed, Feb 10, 2010 at 5:12 PM, r_arun rathakrishnana...@gmail.com wrote: Your algorithm is correct. But 3. Remove the children from this place and store them as BST3 and BST4. This is not required , because trying to merge BST2 with BST1,which is equivalent to finding a place to insert a pointer to root of BST2 in BST1. Whenever you need a place for a new node, you take a place of a existing leaf in BST1 for that new node. So we need not worry about children. Also in a BST there is no configuration for which a new element can not be inserted. So we can just link the pointers and get a merged tree. -- 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.
[algogeeks] Re: Merge two BST in O(n) time with O(1)
Your algorithm is correct. But 3. Remove the children from this place and store them as BST3 and BST4. This is not required , because trying to merge BST2 with BST1,which is equivalent to finding a place to insert a pointer to root of BST2 in BST1. Whenever you need a place for a new node, you take a place of a existing leaf in BST1 for that new node. So we need not worry about children. Also in a BST there is no configuration for which a new element can not be inserted. So we can just link the pointers and get a merged tree. -- 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] Re: Merge two BST in O(n) time with O(1)
or a balanced BST can be made in step 3, in linear time too, if one objects to the skew model. 2010/1/29 ShingRay masterrays...@gmail.com Oh, I have said something wrong. 1. Inorder traverse both trees. This gives two sorted list. Θ(m+n) 2. Merge the two sorted list A, B into a new one C. Θ(m+n) 3. Build a new tree using C. Each node of the tree has just one child. Θ(m+n) -- 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] Re: Merge two BST in O(n) time with O(1)
Hi , I would like to add to what Shing has suggested. Inorder traverse both trees. This gives two sorted list. Θ(m+n) 2. Merge the two sorted list A, B into a new one C. Θ(m+n) 3. Build a new tree using C. Each node of the tree has just one child. Θ(m+n) Use the LeftChild and RightChild pointers in each node for Next and Prev pointers in the linked list. Hence we will not need any additional space as well. That makes it O(1) in space and O(n+m) in running time. Regards Sourashis On Fri, Jan 29, 2010 at 6:40 PM, Ashish Meena ashishmee...@gmail.comwrote: Hi all, Lets say we do following steps to merge two BSTS's. Lets call them BST1 and BST2. 1. Check the value of root of BST2. 2. In BST1 find a place where root of BST2 can be put. 3. Remove the children from this place and store them as BST3 and BST4. 3. Attach BST2's root pointer at this place. We dont have to do anything more for BST2 as all children of BST2 are already at their proper place Now our BST1 has BST2 merged to it but it doesnt have BST3 and BST4. 4. Do inorder traversal of BST3 and BST4 and insert it to BST1. If we know the approximate size of BST1 and BST2 we can choose tree for our step 1 accordingly. This algorithm doesnt need any extra memory and can be almost O(n), if BST3 and BST4 are very small trees. Does anybody see any issues with this approach? Regards, Ashish On Fri, Jan 29, 2010 at 2:52 PM, vivek bijlwan viv...@gmail.com wrote: @ shingray ... cartesian trees are not BSTs . I guess nirmal's question asks for a BST. also cartesian trees have extra space requirements. On Fri, Jan 29, 2010 at 12:07 AM, naga vinod kumar vinodkumark...@gmail.com wrote: hi varun ,it cant be in O(n) time ,it can be merged in O(nlogn) time. On Thu, Jan 28, 2010 at 10:37 PM, Varun S V varun...@gmail.com wrote: Delete the nodes in the second BST in postorder. As and when you delete this node, insert it into the first BST. On Thu, Jan 28, 2010 at 9:35 PM, Bijlwan viv...@gmail.com wrote: hey nirmal . i don't get that when you merge the two linked list , how do you get the BST? making the BST would itself be a O(nlogn) process? On Jan 28, 5:03 am, Nirmal nirm...@gmail.com wrote: Given two binary search trees, how to merge them in O(n) time and O(1) space? It can be done using O(n) space as below, 1. covert BST #1 into linked list or sorted array 2. covert BST #2 into linked list or sorted array 3. merge them... but how to do this in place? -- 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.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.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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Ashish Meena -- 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] Re: Merge two BST in O(n) time with O(1)
hi varun ,it cant be in O(n) time ,it can be merged in O(nlogn) time. On Thu, Jan 28, 2010 at 10:37 PM, Varun S V varun...@gmail.com wrote: Delete the nodes in the second BST in postorder. As and when you delete this node, insert it into the first BST. On Thu, Jan 28, 2010 at 9:35 PM, Bijlwan viv...@gmail.com wrote: hey nirmal . i don't get that when you merge the two linked list , how do you get the BST? making the BST would itself be a O(nlogn) process? On Jan 28, 5:03 am, Nirmal nirm...@gmail.com wrote: Given two binary search trees, how to merge them in O(n) time and O(1) space? It can be done using O(n) space as below, 1. covert BST #1 into linked list or sorted array 2. covert BST #2 into linked list or sorted array 3. merge them... but how to do this in place? -- 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.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] Re: Merge two BST in O(n) time with O(1)
@ shingray ... cartesian trees are not BSTs . I guess nirmal's question asks for a BST. also cartesian trees have extra space requirements. On Fri, Jan 29, 2010 at 12:07 AM, naga vinod kumar vinodkumark...@gmail.com wrote: hi varun ,it cant be in O(n) time ,it can be merged in O(nlogn) time. On Thu, Jan 28, 2010 at 10:37 PM, Varun S V varun...@gmail.com wrote: Delete the nodes in the second BST in postorder. As and when you delete this node, insert it into the first BST. On Thu, Jan 28, 2010 at 9:35 PM, Bijlwan viv...@gmail.com wrote: hey nirmal . i don't get that when you merge the two linked list , how do you get the BST? making the BST would itself be a O(nlogn) process? On Jan 28, 5:03 am, Nirmal nirm...@gmail.com wrote: Given two binary search trees, how to merge them in O(n) time and O(1) space? It can be done using O(n) space as below, 1. covert BST #1 into linked list or sorted array 2. covert BST #2 into linked list or sorted array 3. merge them... but how to do this in place? -- 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.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.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] Re: Merge two BST in O(n) time with O(1)
Hi all, Lets say we do following steps to merge two BSTS's. Lets call them BST1 and BST2. 1. Check the value of root of BST2. 2. In BST1 find a place where root of BST2 can be put. 3. Remove the children from this place and store them as BST3 and BST4. 3. Attach BST2's root pointer at this place. We dont have to do anything more for BST2 as all children of BST2 are already at their proper place Now our BST1 has BST2 merged to it but it doesnt have BST3 and BST4. 4. Do inorder traversal of BST3 and BST4 and insert it to BST1. If we know the approximate size of BST1 and BST2 we can choose tree for our step 1 accordingly. This algorithm doesnt need any extra memory and can be almost O(n), if BST3 and BST4 are very small trees. Does anybody see any issues with this approach? Regards, Ashish On Fri, Jan 29, 2010 at 2:52 PM, vivek bijlwan viv...@gmail.com wrote: @ shingray ... cartesian trees are not BSTs . I guess nirmal's question asks for a BST. also cartesian trees have extra space requirements. On Fri, Jan 29, 2010 at 12:07 AM, naga vinod kumar vinodkumark...@gmail.com wrote: hi varun ,it cant be in O(n) time ,it can be merged in O(nlogn) time. On Thu, Jan 28, 2010 at 10:37 PM, Varun S V varun...@gmail.com wrote: Delete the nodes in the second BST in postorder. As and when you delete this node, insert it into the first BST. On Thu, Jan 28, 2010 at 9:35 PM, Bijlwan viv...@gmail.com wrote: hey nirmal . i don't get that when you merge the two linked list , how do you get the BST? making the BST would itself be a O(nlogn) process? On Jan 28, 5:03 am, Nirmal nirm...@gmail.com wrote: Given two binary search trees, how to merge them in O(n) time and O(1) space? It can be done using O(n) space as below, 1. covert BST #1 into linked list or sorted array 2. covert BST #2 into linked list or sorted array 3. merge them... but how to do this in place? -- 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.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.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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Ashish Meena -- 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.
[algogeeks] Re: Merge two BST in O(n) time with O(1)
Oh, I have said something wrong. 1. Inorder traverse both trees. This gives two sorted list. Θ(m+n) 2. Merge the two sorted list A, B into a new one C. Θ(m+n) 3. Build a new tree using C. Each node of the tree has just one child. Θ(m+n) -- 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.
[algogeeks] Re: Merge two BST in O(n) time with O(1)
A Cartesian tree can be built in Ο(n) time. You can traverse both trees and build another Cartesian tree. On 1月28日, 下午9时03分, Nirmal nirm...@gmail.com wrote: Given two binary search trees, how to merge them in O(n) time and O(1) space? It can be done using O(n) space as below, 1. covert BST #1 into linked list or sorted array 2. covert BST #2 into linked list or sorted array 3. merge them... but how to do this in place? -- 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.
[algogeeks] Re: Merge two BST in O(n) time with O(1)
hey nirmal . i don't get that when you merge the two linked list , how do you get the BST? making the BST would itself be a O(nlogn) process? On Jan 28, 5:03 am, Nirmal nirm...@gmail.com wrote: Given two binary search trees, how to merge them in O(n) time and O(1) space? It can be done using O(n) space as below, 1. covert BST #1 into linked list or sorted array 2. covert BST #2 into linked list or sorted array 3. merge them... but how to do this in place? -- 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.
