In a max-heap whose right subtree is rooted at 36 and currently has leaf nodes…
2022
In a max-heap whose right subtree is rooted at 36 and currently has leaf nodes 25 and 1, a new node with value 15 is inserted as the left child of node 25, the leftmost available position in the right subtree. After insertion and heap adjustment, which values are at the leaf nodes of the right subtree?
- A.
15 and 1
- B.
25 and 1
- C.
3 and 1
- D.
2 and 3
Attempted by 239 students.
Show answer & explanation
Correct answer: A
Step 1: The right subtree is rooted at node 36. Before insertion, its leaf nodes are 25 and 1.
Step 2: The new value 15 is inserted at the leftmost available position in the right subtree, so it becomes the left child of node 25.
Step 3: In a max-heap, compare the inserted node with its parent. Since 15 < 25, the max-heap property is already satisfied and no swap is required.
Step 4: After insertion, node 25 has a child, so it is no longer a leaf. The leaf nodes of the right subtree are 15 and 1.
Final Answer: 15 and 1.