Merge two binary search tree into a balanced BST
Quoted from John_Gaughan in Wu::forum
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1102583054

1. Doing a preorder traversal will, of course, get all elements in ascending order: O(n+m).
2. Merging into another array is trivial: O(n+m).
3. Creating another balanced tree using middle-element method is O(n+m).

So the whole thing is O(n+m).

we don't have to create three intermediate arrays.
Merge the trees into the array on the fly while traversing using the same method as merging two sorted arrays, treating the output of the preorder traversals as serialized arrays.

If we know the size of the original trees, we can forgo the intermediate array entirely by calculating the structure of the target tree and inserting nodes directly where they will wind up. This only works, however, if we have a priori knowledge of the tree's size.
- posted by Pop @ 3:35 PM