@meena that is too specific example that you have taken. such a BST2 can be inserted into BST1 in linear time any which way.
On Fri, Jan 29, 2010 at 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.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<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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
