Merging Two Binary Search Trees I'm looking for an algorithm to merge two binary search trees of arbitrary size and range.  The obvious way I would go about implementing this would be to find entire subtrees whose range can fit into an arbitrary external node in the other tree.  However, the worst case running time for this type of algorithm seems to be on the order of O(n+m) where n and m are the size of each tree respectively.

However, I've been told that this could be done in O(h), where h is the height of the tree with the larger height.  And I'm completely lost on how this is possible.  I've tried experimenting with rotating one the trees first, but rotating a tree into a spine is already O(h).
In ArXiv:1002.4248, John Iacono and Özgür Özkan describe a relatively simple algorithm to merge two binary search trees in $O(\log^2 n)$ amortized time; the analysis is the hard part.  [Update: As Joe correctly observes in his answer, this algorithm is due to Brown and Tarjan.]  They also describe a more complicated dictionary data structure, based on biased skip lists, that supports merges in $O(\log n)$ amortized time. 

On the other hand, a worst-case bound of $O(\log n)$ is impossible.  Consider two binary search trees with $n$ nodes, one storing the even integers between $2$ and $2n$, the other storing the odd integers between $1$ and $2n-1$.  Merging the two trees creates a new binary search tree storing all integers between $1$ and $2n$.  In any such tree, a constant fraction of the nodes have different parity than their parents.  (Proof: The parent of an odd leaf must be even.)  Thus, merging the even and odd trees requires changing $\Omega(n)$ pointers.