algorithm - How to concatenate two binary search tree efficiently?

Question

I am not asking how to merge two binary search trees, as this question did How to merge two BST's efficiently?

I am really asking how to concatenate two trees. So if tree A's all nodes are smaller than any node of tree B, we can concatenate two trees. But how do I do it efficiently?

My idea is to find tree B's minimum, and then let tree A be the left child of minimum(tree B).

This is simple enough and the time is O(height of B).

But I guess this solution has some problems:

1. it may cause the final big tree not balanced any more
2. What if the worst case running time is O(h), where h is the max height of the two tree?

Actually, The book "Algorithm Design Manual" has this excise. Is my simple solution enough for this exercise?

A concatenate operation takes two sets S1 and S2, where every key in S1 is smaller than any key in S2, and merges them together. Give an algorithm to concatenate two binary search trees into one binary search tree. The worst-case running time should be O(h), where h is the maximal height of the two trees.

Thanks

Answer 1

I'm going to define:

• h_A = max height of A
• h_B = max height of B
• h = min(h_A, h_B)

Your solution's worst case running time is O(h_B), which happens when the depth of min(B) is h_B.

The question asked for a O(h_B) worst case. A O(h) solution is preferable, since if h_B is much larger than h_A, we'd be better off attaching B to the right child of max(A) than your current solution, which attaches A to the left child of min(B).

Here's how to do that:

1. Recursively traverse down the right of A, and the left of B.
2. Stop traversing when you get to either max(A) or min(B).
3. One of three things is possible:
4. You got to max(A). In this case, set max(A).right = B
5. You got to min(B). In this case, set min(B).left = A
6. You got to max(A) and min(B). In this case, do either of the above options.

At most we traversed h_A or h_B steps, whichever is smaller. That is, h steps. Attaching one tree to an element is constant. Thus the running time is O(h).