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 the root node III. A max-heap can be constructed from a binary search tree in Θ(n) time IV. A binary search tree can be constructed from a max-heap in Θ(n) time Which of the above statements are TRUE?

Option 1 : I, II and III

Max-heap:

[ alt="GATE CS 112 7Q GATE 2019 images raju D 3" src="//storage.googleapis.com/tb-img/production/19/11/GATE_CS_112_7Q_GATE_2019_images_raju_D%203.PNG">

• Smallest element (12) of the max heap is always at the leaf.
• Second largest element (25) in a max heap is always a child of the root node

Binary Search Tree:

[ alt="GATE CS 112 7Q GATE 2019 images raju D 4" src="//storage.googleapis.com/tb-img/production/19/11/GATE_CS_112_7Q_GATE_2019_images_raju_D%204.PNG">

INORDER: 14, 15, 18, 20, 22, 23, 25, 30

Traversal time complexity = O(n)

Store the element in an array in reverse order

Filling the array in reverse order. Time complexity = Θ(n)

Total time complexity = Θ(n) + Θ(n) = Θ(n)

MAX heap:

[ alt="GATE CS 112 7Q GATE 2019 images raju D 5" src="//storage.googleapis.com/tb-img/production/19/11/GATE_CS_112_7Q_GATE_2019_images_raju_D%205.PNG">

Statement I, II and III are correct

:

A binary search tree can be constructed from a max heap in Θ(n²) time

Assume that distinct elements are present