Algorithm  How to efficiently combine two binary search trees?
I am not asking how to merge two binary search trees, as this question did How to merge two BSTs efficiently?
I am really asking how to combine two trees. Therefore, if tree A of all nodes is smaller than any node of tree B, we can merge the two trees. But how can I do this efficiently?
My idea is to find the minimum of tree B and then let tree A be the left child of the minimum (tree B).
It's simple enough and time consuming O(height of B)
.
But I think this solution has some problems:
 this can cause the final big tree to be out of balance.
 What if the worst running time
O(h)
, whereh
is the maximum height of two trees?
Actually the book " Algorithm Design Guide" has this excise. My simple solution for this exercise?
The concatenation operation takes two sets S1 and S2, where each key in S1 is less than any key in S2, and concatenates them. Provide an algorithm for combining two binary search trees into one binary search tree . In the worst case, the running time should be O (h), where h is the maximum height of two trees.
thank
source to share
I'm going to define:

h_A
= maximum heightA

h_B
= maximum heightB

h = min(h_A, h_B)
Your worst case running time of your solution O(h_B)
, which happens when the depth min(B)
is equal h_B
.
Worst case question O(h)
. Solution A O(h)
is preferred as if there is h_B
much more than h_A
, we'd be better off attaching B
to the correct child max(A)
than your current solution, which attaches A
to the left child min(B)
.
Here's how to do it:
 Recursively navigate to the right of
A
and to the left ofB
.  Stop moving when you go to
max(A)
ormin(B)
.  One of three is possible:
 You are in
max(A)
. In this case, setmax(A).right = B
 You received
min(B)
. In this case, setmin(B).left = A
 You got
max(A)
andmin(B)
. In this case, do one of the above options.
 You are in
At best, steps have been taken h_A
or h_B
, whichever is less. Ie h
. Attaching one tree to an element is permanent. So the running time is O (h).
source to share