ITPEC FE Subject B April 2026 Question 9

A is size + 1 = pow(2, height) and B is getSize(root.left) + getSize(root.right) + 1.

Blank B — a node's subtree size is both subtrees plus the node itself, so the + 1 is essential; without it every call returns 0.

Blank A — a perfect binary tree of height h holds 2ʰ − 1 nodes. Rearranged to avoid the subtraction that is the whole point of the test: size + 1 = 2ʰ.

Check it against small trees, remembering that getHeight returns 0 for an empty tree:

• •one node — height 1, size 1, and 1 + 1 = 2¹
• •root with two children — height 2, size 3, and 3 + 1 = 2²

Answer (b)

Why not others:
- (a), (d) and (g) — omit the + 1 in B, so getSize counts no nodes at all and always returns 0
- (c), (f) and (i) — subtract 1 in B, undercounting every subtree and producing negative sizes
- (d), (e) and (f) — compare against pow(2, height − 1), which is the number of leaves in a perfect tree, not the total node count
- (g), (h) and (i) — compare size directly with pow(2, height), one node too many

Key rule: Verify a size or height formula on the smallest cases. A single node settles whether the exponent needs adjusting and whether the + 1 belongs in the count or in the comparison.

AI-generated — may contain errors