Actually, it doesn't have to be inorder. The naive approach is to traverse
through the smaller tree (using any traversal in|pre|post|level order) and
insert each node into the bigger tree. The order of this would be n2logn1
A better approach is to try and fit as much of the smaller bst into the
larger bst. To explain, imagine the second (and smaller) bst can go and fit
snugly as a leaf of the first bst, then you just need to do a logn1
traversal to find this location to insert the smaller bst into the larger
bst. However you might not always have a spot in the first bst for the
second bst to go as a whole. Here you break up the second tree into three
pieces, root node, left subtree and right subtree. You insert the root node
into BST1 and recursively call the merge on BST1 & LeftSubTreeOfBST2 AND
BST1 and RightSubTreeOfBST2.
I think the worst case of this is not going to be much better than the naive
approach but asymptotically this one should kick ass. ( To ensure that an
adversary cannot make it perform badly, we can decide which BST to use as
bst1 randomly.) Can anyone try and deduce the actual order of this algorithm
(if it works)
merge (bst1, bst2):
if (bst2 is null)
return bst1
if (bst1 is null)
return bst2
if (bst2.max_element < bst1.val)
bst1.left = merge (bst1.left, bst2)
else if (bst2.min_element > bst1.val)
bst1.right = merge (bst1.right, bst2)
else // it means bst2 needs to be split up right away
insertIntoBst(bst1, bst2.val)
bst1 = merge (bst1, bst2.left)
bst1 = merge (bst1, bst2.right)
On Sun, Oct 9, 2011 at 3:38 AM, Vandana Bachani <vandana....@gmail.com>wrote:
> Inorder traversal of one tree insert into another?
>
>
> On Sat, Oct 8, 2011 at 4:33 PM, Ankur Garg <ankurga...@gmail.com> wrote:
>
>> Hi ,
>>
>> Can anyone think of any better for doing this other than converting into
>> List and then converting back again to BST ..
>>
>> Regards
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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.
