In the balanced binary tree shown below, how many nodes will become unbalanced…
1996
In the balanced binary tree shown below, how many nodes will become unbalanced when a new node is inserted as a child of node g?
a
/ \
b e
/ \ /
c d f
/
g
- A.
1
- B.
3
- C.
7
- D.
8
Attempted by 46 students.
Show answer & explanation
Correct answer: B
When a new node is inserted as a child of g, only nodes on the path from g to the root can have their heights changed.
After insertion, the height of the subtree rooted at g increases by 1. Therefore:
- node c becomes unbalanced, because its left subtree is now two levels deeper than its right subtree;
- node b becomes unbalanced, because the height of its left subtree rooted at c increases;
- node a becomes unbalanced, because the height of its left subtree rooted at b increases.
Nodes d, e, and f are not on this path, so their subtree heights do not change.
Thus, the number of nodes that become unbalanced is 3.