0
$\begingroup$

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 !

$\endgroup$
1
  • $\begingroup$ I'd recommend induction. $\endgroup$ Feb 5 '14 at 14:02
2
$\begingroup$

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}$$

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.