Perfect Binary Tree Nodes

Q: How many leaves does a perfect binary tree have?

$2^{h}$ leaves for height $h$, because each row doubles the one above it. Height 3 gives $2^{3} = 8$ leaves, and height 10 gives $2^{10} = 1024$ leaves.

In one sentence: The formula counts every node in a perfect binary tree, a branching diagram in which each row is completely full, using only the number of rows below the top.

$N = 2^{h+1} - 1$

Read it out loud: “N equals 2 to the power of h plus 1, minus 1. N is the total number of nodes, the boxes of the tree. The raised 2 is a power, which means 2 multiplied by itself, the number of times shown in the exponent. The exponent is h plus 1, and the minus 1 is done last. h is the height of the tree, the number of lines from the top box down to the bottom.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Powers of two, like $2^{3}$: A power shows repeated multiplication. $2^{3}$ means 2 multiplied by itself 3 times: $2 \times 2 \times 2 = 8$ . The small raised number is the exponent. Each time the exponent goes up by one, the power doubles: $2^{0} = 1$ , $2^{1} = 2$ , $2^{2} = 4$ , $2^{3} = 8$ . When powers of the same number are multiplied, the exponents add, so $2^{3} \times 2^{1} = 2^{4} = 16$ .
Tree, node, root, child and leaf: A tree is a diagram of boxes joined by lines, with one box at the top. Each box is a node. The top box is the root. A node directly below another is its child, and a node with no children at the bottom is a leaf. A binary tree is one where each node has at most two children, one on the left and one on the right.
Height, measured in edges: An edge is one line joining two nodes. The height of a tree is the number of edges on the longest path from the root down to a leaf. The root alone has height 0, and a root with two children has height 1. Height counts the lines, not the boxes, and that choice changes the exponent in the formula by one.
Levels, or rows: A level is a row of nodes that are all the same number of edges below the root. Level 0 is the root, level 1 holds its children, and so on. The bottom level holds the leaves. A tree of height $h$ has $h + 1$ levels, numbered from 0 to $h$ .
Perfect tree and the dots $\cdots$: A perfect binary tree is one in which every node that is not a leaf has exactly two children, and every leaf sits on the same bottom level. Drawn in rows, every row is completely full. The three dots $\cdots$ mean ‘continue in the same pattern’, so $1 + 2 + 4 + \cdots + 2^{h}$ means add every power of 2 from $2^{0}$ up to $2^{h}$ .

What each symbol means

Symbol	Meaning
$N$	The total number of nodes in the tree: every box, counting the root, the inner nodes and the leaves. It is a plain count with no unit. The example tree has 15 nodes.
$h$	The height of the tree: the number of edges on the longest path from the root down to a leaf. It is a plain count with no unit, and the root alone has height 0. The example uses height 3, which gives four levels, numbered 0 to 3.

The formula piece by piece

$2^{h}$: Start with the bottom level. Each level has double the nodes of the level above it, so level $h$ holds $2^{h}$ nodes, and these are the leaves. At height 3 the bottom level holds $2^{3} = 8$ leaves.
$2^{h+1}$: The exponent is one bigger than the height, because a tree of height $h$ has $h + 1$ levels. Doubling the bottom level’s count does not give the total, but $2^{h+1}$ is the number needed before subtracting one. At height 3 it is $2^{4} = 16$ .
$N = 2^{h+1} - 1$: The whole formula as one sentence: the number of nodes in a perfect binary tree equals two to the power of one more than its height, minus one. For height 3 that is $2^{4} - 1 = 16 - 1 = 15$ nodes.
$1 + 2 + 4 + \cdots + 2^{h}$: The same total written level by level. The root has 1 node, level 1 has 2, level 2 has 4, and so on, down to the bottom level with $2^{h}$ nodes. Adding every level gives the same count as the formula, which is the second way to see why the formula works.

What the formula is doing, and why

A binary tree is a set of nodes where each node has at most two children. A perfect binary tree is one where every inner node has exactly two children and every leaf sits at the same depth. Drawn in rows, every level is completely full, with no gaps.

Counting levels. Define the height $h$ as the number of edges from the root down to the bottom. The root alone has height 0. Level $k$ is the row of nodes that are $k$ edges below the root, so level 0 is the root. The bottom level is level $h$ , and there are $h + 1$ levels in all.

Why doubling? Each node on one level has two children on the next level. So level 0 has $2^{0} = 1$ node, level 1 has $2^{1} = 2$ nodes, and level 2 has $2^{2} = 4$ nodes. In general, level $k$ has $2^{k}$ nodes. Every new level doubles the count of the level above it, which is why the total grows so fast.

Why is the sum one less than a power of two? Adding every level from 0 to $h$ gives $1 + 2 + 4 + \cdots + 2^{h}$ . Each term is double the one before it, and a list like this always adds up to one less than the next power of two. Check with $h = 2$ : $1 + 2 + 4 = 7$ , and $2^{3} - 1 = 7$ . So the total is $2^{h+1} - 1$ . The $+1$ in the exponent comes from the $h + 1$ levels, and the $-1$ comes from this sum.

How big does it get? The count grows fast, because each new level doubles the bottom row. A perfect binary tree of height 20 has $2^{21} - 1$ nodes, which is 2,097,151 nodes. Each extra level of height roughly doubles the total.

An everyday picture

Think of a knockout tournament bracket with eight team slots. The final is the root, two semifinals sit below it, four quarterfinals below those, and eight team slots form the bottom row. Each game is an inner node, and each team slot is a leaf. There are 7 games, and the 8 team slots plus the 7 games make 15 nodes, which is exactly what $2^{3+1} - 1$ gives.

Worked example: A knockout bracket with 8 team slots

A knockout tournament with 8 team slots is drawn as a perfect binary tree. The final is the root, and each team slot is a leaf at the bottom. The tree’s height is $h = 3$ : going from the final down to a team slot takes 3 lines. The example uses simple counts, so each row can be counted by hand.

Read the height. The final is the root at the top, and a team slot is a leaf at the bottom. Going from the final down to any team takes 3 lines, so the height is $h = 3$ . That gives four rows, numbered 0 to 3, with row 3 holding the team slots.
Count the nodes on each row. Row 0 holds $2^{0} = 1$ node, the final. Row 1 holds $2^{1} = 2$ semifinals. Row 2 holds $2^{2} = 4$ quarterfinals. Row 3 holds $2^{3} = 8$ team slots. Each row has double the count of the row above it, because each game has two slots feeding into it.
Add the rows. $1 + 2 + 4 + 8 = 15$ nodes in total. The 8 team slots are the leaves on the bottom row. The other nodes, 1 + 2 + 4 = 7, are games, because a game is an inner node that joins two slots.
Use the formula in one step. $N = 2^{h+1} - 1 = 2^{3+1} - 1$ . The exponent is $3 + 1 = 4$ , and $2^{4} = 2 \times 2 \times 2 \times 2 = 16$ . Subtracting 1 gives $16 - 1 = 15$ nodes, the same as the row total from the previous step.
Count the games. There are 15 nodes in all, and 8 of them are team slots, so the games are $15 - 8 = 7$ . This matches a general rule for knockouts: a bracket with $n$ teams has $n - 1$ games, here $8 - 1 = 7$ .
Check the bottom row. The bottom row is $2^{h} = 2^{3} = 2 \times 2 \times 2 = 8$ . Eight team slots fill it with no gaps, which is what makes the tree perfect. If a slot were missing, the tree would have fewer nodes than the formula gives.
Say it plainly. An 8-team knockout has 15 nodes: 8 team slots and 7 games. The formula found that total from the height alone, so there is no need to count every row, although counting the rows is a good way to check the answer.

Answer: The tree has 15 nodes in total: 8 team slots on the bottom row and 7 games above them. The formula gives the total from the height alone, $2^{3+1} - 1 = 15$ .

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Counting the root as height 1. Height counts edges, so the root alone has height 0. This off-by-one error is one of the most common mistakes with this formula.
Leaving out the $+1$ in the exponent. Using $2^{h} - 1$ gives 7 for $h = 3$ instead of 15. The formula needs $2^{h+1}$ , because a tree of height $h$ has $h + 1$ levels.
Using the formula for a tree that is not perfect. If some leaves sit higher than others, or a row has a gap, the tree has fewer nodes than the formula gives.
Mixing up nodes and edges. A tree with $N$ nodes always has $N - 1$ edges, because each edge joins a node to its parent, and every node except the root has exactly one parent.

Where you will meet it

Analyzing binary search trees and heaps, where the height decides how many steps a search or an insert can take.
Tournament brackets and other knockout trees, where each leaf is a competitor and each inner node is a match.
Estimating the memory a tree of fixed height needs, since each node takes about the same amount of space.
Proving facts about tree-shaped data by counting levels, as in the textbook arguments about how fast tree operations run.

Questions people ask

Is a perfect binary tree the same as a complete binary tree?

No. A perfect tree has every row full. A complete tree fills every row except possibly the last, and the last row fills from the left with no gaps. Every perfect tree is complete, but not every complete tree is perfect.

How many leaves does a perfect binary tree have?

$2^{h}$ leaves for height $h$ , because each row doubles the one above it. Height 3 gives $2^{3} = 8$ leaves, and height 10 gives $2^{10} = 1024$ leaves.

Why is there a +1 in the exponent?

A tree of height $h$ has $h + 1$ rows, because height counts edges and the rows are numbered from 0 to $h$ . The sum of all the rows is $2^{h+1} - 1$ , so the exponent must be one bigger than the height.

Binary Search Steps: Binary search finds an item in a sorted list by checking the middle and throwing away half, and this formula counts how many checks that takes at most.
Binary Number Value: Binary uses only the digits 0 and 1, and this formula turns a row of those digits into the ordinary number they stand for.
Euler's Formula for Planar Graphs: Euler’s formula says that if you draw a connected network on a flat sheet with no crossing lines, then corners minus lines plus regions always comes to 2.