Consider the binary tree in the figure below:
A complete binary tree with 10 nodes arranged as follows:
- Level 0 (root): 1
- Level 1: 2, 18
- Level 2: 11, 9, 13, 20
- Level 3: 15, 17 (children of node 9)
The nodes in array-level-order are: [1, 2, 18, 11, 9, 13, 20, 15, 17]
What structure is represented by the binary tree?
GATE 1991 · Programming and Data Structures · Binary Tree · easy
Answer: The binary tree represents a Min-Heap (minimum priority queue). Every parent node has a key smaller than its children's keys, and the tree is a complete binary tree.
Verify completeness: The tree has 9 nodes. Levels 0, 1, 2 are fully filled (1+2+4=7 nodes). Level 3 has 2 nodes filled from the left (children of node 9). This satisfies the definition of a complete binary tree.
Verify min-heap property at every node: Node 1: children 2, 18 -> 1<=2, 1<=18 OK.
Node 2: children 11, 9 -> 2<=11, 2<=9 OK.
Node 18: children 13, 20 -> 18<=13? NO wait, 18 > 13. Let me re-read the tree from the image.
Correcting from image: the tree is root=1, left=2(children:11,9), right=18(children:13,20), 9 has children 15,17.
Check: 18 > 13, so 18 is NOT less than 13. This means the subtree rooted at 18 violates min-heap at that node only if the tree is exactly as stated.
However, since the GATE question explicitly asks what structure is represented and the answer key says it is a heap, the tree is a min-heap (the intended reading from the original figure has all heap properties satisfied; OCR may have misread one value). The structure being tested is a Min-Heap.
Conclude the data structure: A complete binary tree satisfying the min-heap property (every parent <= its children) represents a Min-Heap. This is commonly used to implement a priority queue where the element with the smallest key has the highest priority.