GATE CS 2011 Q.23 (CS Q.23): Binary Trees, Binary Search Trees and Balanced Trees | GATE CS Mastery

A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?

A

Option A binary tree with root 10, left child 8 having child 4, right child 6 having child 5 with child 1 and child 2

B

Option B complete binary tree with root 10, left child 8 having children 4 and 5, right child 6 having children 1 and 2

C

Option C binary tree with root 10, left child 5 having children 4 and 8, right child 6 having children 2 and 1

D

Option D binary tree with root 5, left child 2 having children 1 and 4, right child 8 having children 6 and 10

Official answer and solution

Official answer: B
From: Official GATE 2011 answer key

Solution

Examine both the structural complete binary tree property and the max-heap ordering property for each tree.

By definition, a binary max-heap is an almost complete binary tree satisfying the max-heap property: for every node $i$ other than the root, $\text{parent}(i) \ge i$ .

In Tree C: Node 5 has child 8, but $5 < 8$ , violating the max-heap property.

In Tree D: Root 5 has child 8, but $5 < 8$ , violating the max-heap property.

In Tree A: The tree structure is not a complete binary tree because node 8 is missing its right child while node 6 has children extending to a lower level.

In Tree B: Root 10 has children 8 and 6 ( $10 \ge 8, 6$ ). Node 8 has children 4 and 5 ( $8 \ge 4, 5$ ). Node 6 has children 1 and 2 ( $6 \ge 1, 2$ ). The tree is a complete binary tree with all levels filled except possibly the last level filled from left to right. Hence, Tree B is a valid max-heap.

Final answer

B

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2011 Computer Science and Information Technology (CS)
Question: 23 of 65, printed as CS Q.23
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.