# 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)`

, where `h`

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

+3

source to share

Let A be a smaller set. Suppose x = maximum_element (A) and y = minimum_element (B).

We know that x <y. take a node with key value equal `z = (x+y)/2`

and make A its left subtree and B its right subtree. remove the added node (with key `z`

) from this BST.

+7

source

I'm going to define:

• `h_A`

= maximum height `A`

• `h_B`

= maximum height `B`

• `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 of `B`

.
• Stop moving when you go to `max(A)`

or `min(B)`

.
• One of three is possible:
• You are in `max(A)`

. In this case, set`max(A).right = B`

• You received `min(B)`

. In this case, set`min(B).left = A`

• You got `max(A)`

and `min(B)`

. In this case, do one of the above options.

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).

+2

source

All Articles