# Number of nodes in binary tree given number of leaves

How would I prove that any binary tree that has n leaves has precisely $2n-1$ nodes ?

Given that a binary tree is either a single node "o" or a node with the left and right subtrees contains a binary tree

     o
/       \
binary  binary
tree    tree


Any help would be appreciated !

• I'd recommend induction. Feb 5 '14 at 14:02

Your formula only works if you assume all the leaves are the same depth in the tree and every node that isn't a leaf has 2 children (see wikipedia for different kinds of binary trees). For example imagine a tree

o
\
o


This has $n=1$ leaves and 2 nodes but the formula gives $2n-1=1$.

Making this assumption, to prove by induction, notice (1) that the formula holds true for a tree of height 1 with 1 node, because $2\times 1 - 1 = 1$.

Then (2) assume that the formula holds for trees with $k$ leaves, so assume trees with $k$ leaves have $2k-1$ nodes. Adding another level to the tree with $k$ leaves adds another $2k$ leaves because each leaf in the original tree has 2 children. So this new tree has a total of $2k-1$ leaves from the original plus another $2k$ leaves = $4k-1$ leaves. The formula for $2k$ leaves gives $2(2k)-1=4k-1$ leaves, which is the same!

So because our (1) our base step is true; and (2) our inductive step is true, then the formula is true for all $n$ (subject to the constraint above).

Alternatively, the depth $d$ of the tree is $\log_2 n +1$ because the number of nodes doubles at each level.

The total number of nodes is $1 + 2 + 4 + \ldots$ with $d$ terms in the sum, or $2^0 + 2^1 + 2^2 + \ldots + 2^{d-1}$. By the geometric series formula the sum is equal to

\begin{align}\frac{2^d -1}{2-1} &= 2^{\log_2 (n+1)} - 1 \\&= 2\times2^{\log_2 n} -1\\&= 2n -1\end{align}

The number of nodes would be $2^{l-1}$, where $l$ is the number of leaf nodes.