6

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

Community
  • 1
  • 1
Jackson Tale
  • 25,428
  • 34
  • 149
  • 271

2 Answers2

10

Let A be the smaller set. Assume x = maximum_element(A) and y = minimum_element(B).

We know x < y. take a node with key value equal to 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.

a-z
  • 1,634
  • 4
  • 16
  • 35
  • 1
    just to be clear, this is better than your answer, Jackson, because it's less likely to unbalance things. – andrew cooke Mar 07 '12 at 22:22
  • 1
    @andrewcooke, yes, you are right. Just make the answer more clear here: after find x and y, delete y from B, and let y be the new root, y.right = B.root, y.left = A.root. I guess this description is more clear than involving a temp z node. thanks – Jackson Tale Mar 26 '12 at 16:45
  • There are two problems with this answer: 1. You don't know which tree is smaller, and can't determine that in O(h) time. 2. The solution asks for a O(h) solution, without regard for balancedness. –  Sep 19 '13 at 11:02
  • @Tom, we can actually determine this in `O(h)` time, because `h` is the maximal height of the two trees. Therefore I think that Jackson's answer is also acceptable, but this one produces better (in terms of balance) result-tree. I also like your answer for minimum height – E. Shcherbo Mar 16 '21 at 07:28
4

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

  • Why do you have `h = min(h_A, h_B)` if in the question `h` is defined as the **maximal** height of the two trees? – E. Shcherbo Mar 16 '21 at 07:22
  • "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)." –  Feb 24 '22 at 10:11