GATE CS 2019 Q40 — Binary Heaps

Let us analyze each statement individually:

• Statement I: The smallest element in a max-heap is always at a leaf node. (TRUE)
  In a max-heap, the parent node is always greater than or equal to its children. If the smallest element were an internal node, its children would have to be smaller than or equal to it, which contradicts the assumption that it is the smallest element. Thus, the minimum element must reside in one of the leaf nodes.


• Statement II: The second largest element in a max-heap is always a child of a root node. (TRUE)
  The root node contains the largest element of the heap. Since any node in the heap is less than or equal to its parent, the second largest element cannot be further down the tree (as it would be smaller than its ancestors). Therefore, it must be one of the direct children of the root (either the left child or the right child).


• Statement III: A max-heap can be constructed from a binary search tree in $\Theta(n)$ time. (TRUE)
  We can perform an in-order (or any) traversal of the BST to copy its $n$ elements into an array in $\Theta(n)$ time. Then, we can apply the standard bottom-up Build-Max-Heap algorithm on this array, which runs in $\Theta(n)$ time. Thus, the overall construction takes $\Theta(n)$ time.


• Statement IV: A binary search tree can be constructed from a max-heap in $\Theta(n)$ time. (FALSE)
  If we could construct a BST from a max-heap in $\Theta(n)$ time, we could sort $n$ elements in $O(n)$ comparison-based time as follows:
  1. Build a max-heap from $n$ unsorted elements in $O(n)$ time.
  2. Convert the max-heap to a BST in $O(n)$ time.
  3. Perform an in-order traversal of the BST in $O(n)$ time to get the sorted order.
  This would violate the $\Omega(n \log n)$ lower bound for comparison-based sorting. Hence, this conversion is not possible in $\Theta(n)$ time.

Since statements I, II, and III are true, the correct option is A.