Merging two binary search tress

Question

You have two binary search trees A and B, each one is a complete binary tree containing $2^k-1$ nodes. The maximum value of the keys in the tree A is less than the minimum value of the keys in tree B.

Propose an efficient algorithm for creating a single height-balanced binary search tree containing the key values of all the nodes in both the trees A and B.

Answer 1

Begin by computing the heights h1 of T1 and h2 of T2. This takes time O(h1 + h2): You simply traverse a path from the root, going to left child if the balance factor is -1, to the right child if it is positive, and to any of the children if the balance factor is 0, until you reach a leaf. Assume that h1 􏰁 h2; the other case is symmetric.

Next, DELETE the smallest element x from T2, leaving T2′ of height h. This takes O(h2) time.

Find a node v on the rightmost path from the root of T1, whose height is either h or h + 1, as follows:

v ← root(T1)
h′ ← h1
  whileh′ >h+1do
  if balance factor (v) = -1 then h′ ← h′ − 2
  else h′ ← h′ − 1
  v ← rightchild(v)

This takes O(h1) time. Let u denote the parent of v.

Form a new tree whose root contains the key x, whose left subtree is the subtree rooted at v and whose right subtree is T2′. Note that this is a valid binary search tree, since all the keys in the subtree rooted at v are in T1 and, hence, smaller than x, and, by construction, x is smaller than or equal to all elements in T2′. The balance factor of the root of this new tree is h−h′, which is either -1 or 0, so this new tree is a valid AVL tree. The height of this new tree is h′ +1, which is 1 bigger than v’s height. Let the root of this new tree be the right child of u, in place of v. Again, since all keys in this new tree are at least as big as u, this results in a valid binary search tree. This part of the construction takes constant time.

Now, as in the INSERT algorithm, we go up the tree, starting at u, fixing balance factors and perhaps doing a rotation. This takes O(h1) time. Note that the correctness follows from the condition at u before this process is begun is a condition that can arise during the INSERT algorithm. Since h1, h2 ∈ O(log n), the total time taken by this algorithm is in O(log n)

you can find more answer in this question : Merging of height balanced trees

and this algorithm can help you for more details : A Fast Merging Algorithm MARK R. BROWN