A concatenate operation takes two sets, such that all keys in one set are smaller than all the keys in the other set, and merges them together. Suppose T1 and T2 are binary search trees where all the keys in T1 are smaller than all the keys in T2.
Design an algorithm that concatenates T1 and T2 into a single binary search tree.
The worst case running time should be O(h), where h is the maximum of h1 and h2, the heights of T1 and T2.