...
Teaching-Aptitude
October 4, 2023
Teaching Aptitude
October 4, 2023
Teaching-Aptitude
October 4, 2023
Teaching Aptitude
October 4, 2023

GATE 2019

Question 41
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?
A
I, II and III
B
II, III and IV
C
I, III and IV
D
I, II and IV
Question 41 Explanation: 
i) TRUE: The smallest element in heap is always a leaf node but depends upon the graph, it may be left or right side of the graph.
(ii) TRUE: The second smallest element in a heap is always a child of root node.

(iii) TRUE: Converting from binary search tree to max heap will take O(n) time as well as O(n) space complexity.
(iv) FALSE: We can’t convert max heap to binary search tree in O(n) time.

Correct Answer: A
Question 41 Explanation: 
i) TRUE: The smallest element in heap is always a leaf node but depends upon the graph, it may be left or right side of the graph.
(ii) TRUE: The second smallest element in a heap is always a child of root node.

(iii) TRUE: Converting from binary search tree to max heap will take O(n) time as well as O(n) space complexity.
(iv) FALSE: We can’t convert max heap to binary search tree in O(n) time.

Leave a Reply

Your email address will not be published. Required fields are marked *