Let's analyze each statement carefully: ### Statement I: **"The smallest element in a max-heap is always at a leaf node** - ****: In max-heap, the is the maximum element. The smallest element must be at a leaf node because: - Non-leaf nodes have children larger or equal to themselves (by heap property). - The smallest element tends to be among the leaves, as they are at the bottom and have fewer constraints. ### Statement II: **"The second largest element in a max-heap is always a child of the root node."** - **True**: Since the root is the maximum element, its children are the next candidates for the second largest element. The second largest element must be among the root's children because: - Heap property guarantees children are less than or equal to the parent. - The second largest element cannot be elsewhere in the heap without violating the heap property. ### Statement III: **"A max-heap can be constructed from a binary search tree in Θ(n) time."** - **True**: Constructing a max-heap from a binary search tree (BST): - First, perform an inorder traversal of the BST to get sorted elements (O(n)) - Then, build a heap from these elements in O(n) using the heapify process. - The combined process can be optimized to O(n). ### Statement IV: **"A binary search tree can be constructed from a max-heap in Θ(n) time."** - **False**: Constructing a BST from a heap is not straightforward: - The heap does not preserve the in-order sequence needed for a BST. - Building a BST from an arbitrary array (heap elements) generally takes O(n log n) time unless the data is sorted. - Since the heap does not necessarily store elements in in-order, constructing a BST cannot be guaranteed in Θ(n). --- ### **Conclusion:** - Statements **I, II, and III** are **true**. - Statements **IV** is **false**. **Correct answer:** > **I, II, and III**