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 constr

Question

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?

Accepted Answer

I, II and III. In a max-heap the smallest element is at a leaf (I true) and the second largest must be a child of the root (II true). Building a max-heap from any array (including a BST's nodes) is Theta(n) (III true). Building a BST from a max-heap in Theta(n) would sort in linear time, which is impossible (IV false). So I, II and III, index 0, not the stored option.

Solution

Related GATE Technical questions