GATE CS 2005 Q34 — Binary Heaps

To find the level-order traversal after inserting the elements, we perform the standard binary heap insertion operations step-by-step.

Step 1: Initial Max-Heap

The initial level-order traversal is 10, 8, 5, 3, 2. Represented as a complete binary tree, it looks like this:

       10
      /  \
     8    5
    / \
   3   2

Step 2: Insert 1

1. Insert 1 at the next available position in the complete binary tree (as the left child of 5):

          10
         /  \
        8    5
       / \  /
      3   2 1
     

2. Compare 1 with its parent 5. Since $1 \le 5$, the max-heap property is satisfied, and no swap is required.

Step 3: Insert 7

1. Insert 7 at the next available position (as the right child of 5):

          10
         /  \
        8    5
       / \  / \
      3   2 1  7
     

2. Compare 7 with its parent 5. Since $7 > 5$, we swap them to restore the max-heap property:

          10
         /  \
        8    7
       / \  / \
      3   2 1  5
     

3. Compare 7 with its new parent 10. Since $7 \le 10$, the heap property is satisfied, and no further swaps are needed.

Conclusion

The final level-order traversal of the heap is obtained by reading the tree level-by-level from left to right:

$$\mathbf{10,\, 8,\, 7,\, 3,\, 2,\, 1,\, 5}$$

This matches Option D.