Consider the following statements: I. The smallest element in a max-heap is…

Answer: I, II and III

• I — True (with a caveat): Under the usual assumption of distinct keys, the smallest element must be at a leaf because any internal node has a child with value less than or equal to it, so a strictly smaller element cannot be above a child. If equal keys are allowed, equal minima could appear at internal nodes.

• II — True: The second-largest element must be one of the root's children because every node in a subtree beneath a child is ≤ that child, so the maximum among all non-root nodes is the maximum among the root's children.

• III — True: Convert the BST to an array by any tree traversal in Θ(n), then use the standard linear-time heap-building algorithm (heapify) which runs in Θ(n). Together this yields Θ(n).

• IV — False: Constructing a binary search tree from an arbitrary max-heap would require arranging elements into sorted order (or performing repeated insertions), which in the comparison model costs Ω(n log n) in the worst case, so Θ(n) cannot be guaranteed.