The number of nodes in a complete binary tree of height h (with the root at…

Concept — in any binary tree the root sits alone at level 0 and every node has at most two children, so each level can hold at most twice as many nodes as the level above it. Level i therefore holds at most 2i nodes. When a binary tree of height h is filled to that maximum on every level — height being the number of edges on the longest root-to-leaf path — the levels present are exactly 0, 1, …, h, and there is no level deeper than h.

Application — count the nodes level by level for a tree of height h:

1. Level 0 holds 20 = 1 node, the root.

2. Level 1 holds 21 = 2 nodes, level 2 holds 22 = 4 nodes, and each further level doubles.

3. The deepest level, level h, holds 2h nodes.

4. Adding one term per level over levels 0 through h gives the total 20 + 21 + … + 2h.

5. That is a geometric series with first term 1 and common ratio 2, so its closed form is 2h + 1 − 1.

Cross-check — for h = 0 the tree is just the root, so the sum is 20 = 1 and the closed form gives 21 − 1 = 1. For h = 2 the levels are 0, 1 and 2 with 1 + 2 + 4 = 7 nodes, and the closed form gives 23 − 1 = 7.

Contrast — how the other expressions differ from this level-by-level count:

• 20 + 21 + … + 2h − 1 adds up to 2h − 1 and stops at level h − 1, so the deepest level h is never counted.

• 20 + 21 + … + 2h + 1 adds up to 2h + 2 − 1 and includes a level h + 1, which a tree of height h does not have.

• 21 + … + 2h + 1 adds up to 2h + 2 − 2; it drops the root term 20 and also counts a level h + 1 that does not exist.

Terminology note — some texts reserve the word "complete" for a tree whose deepest level may be only partly filled, in which case the node count is not fixed by h alone; that is why the stem states that every level is completely filled.

Result — the number of nodes in such a tree is 20 + 21 + … + 2h, which equals 2h + 1 − 1.