Strictly binary tree has 2n-1 nodes

A strictly binary tree is a binary tree in which every node has either 0 or 2 children (no node has exactly one child).

Claim: a strictly binary tree with n leaves has 2n − 1 nodes.

Proof 1 (counting)

Let n be the number of leaves and m the number of non-leaf (internal) nodes, so the total is N = n + m.

• Every internal node has exactly 2 children, so the number of child links is 2m.
• Every node except the root is the child of exactly one node, so the number of child links is N − 1.

Therefore 2m = N − 1 = n + m − 1, giving m = n − 1.

Total nodes N = n + m = n + (n − 1) = 2n − 1. ∎

Proof 2 (induction on n)

• Base case: n = 1. The tree is a single node (the root is a leaf), so N = 1 = 2(1) − 1. ✓
• Inductive step: assume every strictly binary tree with fewer than n leaves (n > 1) has 2k − 1 nodes for k leaves. Remove the root of the given tree; its two subtrees are strictly binary trees with n₁ and n₂ leaves, where n₁ + n₂ = n and n₁, n₂ ≥ 1. By hypothesis they have (2n₁ − 1) and (2n₂ − 1) nodes. Adding the root: N = 1 + (2n₁ − 1) + (2n₂ − 1) = 2(n₁ + n₂) − 1 = 2n − 1. ✓ ∎

Example: root with two leaves has n = 2 and 3 nodes = 2(2) − 1.