The question is, basically, what would be an example of two balanced binary search trees that cannot be merged in logarithmic time?
Motivation:
Suppose we have two balanced binary search trees T1 and T2 with n and m nodes respectively. Their depth is logarithmic (O(log n) and O(log m) respectively). Suppose n <= m.
If the intervals of values of T1 and T2 do not overlap, i.e., max T1 < min T2 (or max T2 < min T1), joining those trees can be really efficient (O(log m)) if we use, e.g., Splay trees or Treaps.
Otherwise, the best algorithm I am aware of is a linear O(n + m) algorithm (inorder traversal of both trees followed by merging the values and the creation of a new balanced tree).
This is much worse than logarithmic but (while doodling around) I could not find two trees of size n (for some arbitrary large n) where it would be necessary to use this algorithm.
Make one a balanced binary tree of length m of the even numbers in the range 2..2m. Make the other a balanced binary tree of length m of the odd numbers in the range 1..2m-1.
The merged binary tree needs to wind up with O(m) nodes with values from the one tree with children are from the other tree. And therefore you cannot merge without constructing at least O(m) new nodes, which takes O(m) time.