Merge two Binary Search Trees

How efficiently can we merge two binary search trees?
Naive method such as tearing off nodes one by one from 2nd tree and inserting into first tree is not desired.

Are there any special properties of these two trees we should know about?

What about special cases, like
- merging two identical trees
- merging two trees where a simple root->left = t1 and root->right = t2 suffices


What are you hoping to gain when you've done it?
It's still going to be O(logn) whether you search one tree or two trees.

Unless your trees substantially overlap (which would involve an iterative remove / search / insert anyway), you're not going to reduce n by a significant amount.

In any event, if you were doing a search, you would stop at search(t1) if what you were looking for was found, and NOT do search(t2), even if t2 happens to also contain what you're looking for.

>How efficiently can we merge two binary search trees?
O(N + M) where N is the size of the first tree and M is the size of the other. It's done by flattening the trees into arrays, merging the arrays, then generating a new tree from the merged result.

But the thing is we are either destroying the trees or using extra space for doing so.
Can we do in O(log n + log m)? Is it possible?

>But the thing is we are either destroying the trees or using extra space for doing so.
Yes, there are no other options. Either you destroy the trees and reuse the memory they take up, or you duplicate the data and use extra space.

>Can we do in O(log n + log m)? Is it possible?
No. the best you can do is O(N + M) if the binary search tree ordering property needs to be maintained. You can do it in place by deconstructing the trees as you go, flattening them into degenerate trees (linked lists), and finally merging them in the typical manner. This is essentially the same solution as merging two arrays and creating a new tree, though more complicated due to the breakdown of the original trees mid-process.