Q21: Last but one element in Max-heap

This is in continuation with our previous question (#20).

Question #21: At what level will the next to smallest element be present in a binary max-heap?

Options:

1. Last level only

2. Last or second last level only

3. Depends on the number of levels

4. Depends on the total number of nodes

Solution: The correct answer is 2. Keeping in mind that heap is a full binary tree except the last level, we can see that the next to smallest element can only have 1 child – i.e. the smallest element. Therefore it can only be present at second last level in that case, otherwise it will be present on the last level.