If we implement the heap as a Max Heap, and add a new node with value 15 to the leftmost node of the right subtree, what will be the values at the leaf nodes in the right subtree of the heap?

Question

If we implement the heap as a Max Heap, and add a new node with value 15 to the leftmost node of the right subtree, what will be the values ​​at the leaf nodes in the right subtree of the heap?

UpScorer · Accepted Answer

Option (B) 25 and 1. Explanation: The given tree is a max heap because each parent node is larger than its child nodes:
100 > 19, 36
19 > 17, 3
36 > 25, 1
17 > 2, 7

In a max heap, the new node is always inserted at the next available location (so that the full binary tree property is maintained).

The new value 15 will be inserted at the next available location, which is the left child of node 3.

100
          /\
        19 36
       / \ / \
     17 3 25 1
    / \ /
   2 7 15

Compare 15 with its parent (3).
Since 15 > 3, swap them.
Compare 15 with its new parent (19).
Since 15 < 19, no further swapping is necessary.

Final Max Heap:

100
          /\
        19 36
       / \ / \
     17 15 25 1
    / \ /
   2 7 3

The right subtree starts at node 36.

36
    /\
  25 1

Leaf nodes are nodes that have no children.
Therefore, the leaf nodes of the right subtree are: 25 and 1.

Answer

Option: 15 and 1

Answer

Option: 3 and 1

Answer

Option: 2 and 3