Merging two Binary Search Trees

Describe a method to merge two BSTs.

             50
           /    \
          30     70
         /  \   /  \
        20  40 60   80
       /  \           \
      10   25         90


               30
              /   \
            15    45
              \
              20

Answer:

Probably the most efficient:
1. Create two array from the two trees by traversing in inorder: O(n+m) space + O(n+m) time
2. Merge the two arrays: O(n+m) time, O(n+m) space.
3. Create a balanced binary tree from this sorted array ¹, O(n+m) time (see related solution)