In a binary tree, for every node the difference between the number of nodes in…

Answer: The minimum number of nodes for height h > 0 is 2^{h-1} + 1.

Reasoning (define N(h) = minimum nodes for height h):

• Base case: For height 1 (one edge from root to deepest leaf), the minimal tree has 2 nodes, so N(1) = 2.

• Recurrence: To get height h, one child must have height h-1 and at least N(h-1) nodes. The other child can be as small as allowed by the rule that subtree node counts differ by at most 2, so it must have at least N(h-1) - 2 nodes (but not less than 0). Thus for h > 1,

• N(h) = 1 (root) + N(h-1) + (N(h-1) - 2) = 2·N(h-1) - 1.

• Solve by induction: with N(1) = 2, assume N(k) = 2^{k-1} + 1. Then

• N(k+1) = 2·N(k) - 1 = 2·(2^{k-1} + 1) - 1 = 2^{k} + 1.

• Therefore for all h ≥ 1, N(h) = 2^{h-1} + 1, which matches the correct option.