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.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 algoge...@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 algoge...@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 algoge...@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. > -- 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.
