**Question:**

Suppose two binary trees, T1 and T2, hold entries satisfying the heap-order property (but not necessarily the complete binary tree property). Describe a method for combining T1 and T2 into a binary tree T, whose nodes hold the union of the entries in T1 and T2 and also satisfy the heap-order property. Your algorithm should run in time O(h1 +h2) where h1 and h2 are the respective heights of T1 and T2.

**Answer:**

The idea is to treat the two binary trees as the two subtrees of a heap that has its greatest element removed.

——Algorithm:

Create a new binary tree node and attach T1 and T2 as left and right subtree.

Heapify by selecting the greatest of rootT1 and rootT2 and put that item in the new root.

Repeat the process for rootT1 or rootT2, depending on which one was selected in step 2, and so on, until the heap is restored.

—–Complexity:

A binary tree node can be created in O(1).

This is done in constant time. O(1)

Every step takes constant time, O(1), and for each step, we descend one level in the tree (since the item picked to replace the one that used to be in the node we’re in is taken from that node’s children). This means that we’ll do a number of steps equal to the height of the tree. Since we don’t know whether we’ll descend into T1 or T2, this will take O(Max{H1, H2}) which is O(H1 + H2).

The total is then O(1) + O(1) + O(1)O(H1 + H2) = O(H1 + H2)

—-Correctness:

The heap property holds for T1 and T2, meaning that the roots are greater than the items in their trees. Since the greatest of the two roots is picked to be the new root, the new root will be greater than all items in both subtrees.

The same argument can then be repeated for each step in the heapify process.

Thus the heap property will hold for the resulting tree.