Question-29

Consider the following statements: I. The smallest element in a max-heap is always at a leaf node. II. The second largest element in a max-heap is always a child of a root node. III. A max-heap can be constructed from a binary search tree in \(\Theta(n)\) time. IV. A binary search tree can be constructed from a max-heap in \(\Theta(n)\) time. Which of the above statements are TRUE?

• I, II and III
• I, II and IV
• I, III and IV
• II, III and IV

Answer

• I, II and III
• I, II and IV
• I, III and IV
• II, III and IV

Solution

Let’s evaluate each statement:

1. The smallest element in a max-heap is always at a leaf node.
   • True. In a max-heap, the smallest element will be at a leaf node as all parent nodes have larger values than their children.
2. The second largest element in a max-heap is always a child of a root node.
   • True. In a max-heap, the second largest element will be a child of the root node as it’s among the children of the largest element (root).
3. A max-heap can be constructed from a binary search tree in \(\Theta(n)\) time.
   • True. A max-heap can be constructed from a binary search tree in linear time complexity by performing heapify which takes \(\Theta(n)\) time.
4. A binary search tree can be constructed from a max-heap in \(\Theta(n)\) time.
   • False. It takes \(\Theta(n\log n)\) time

Therefore, the statements I, II, and III are TRUE.