Why does a full binary tree of $n$ leaves have $2n-1$ nodes?

A complete binary tree is defined as a tree where each node has either $2$ or $0$ children.

A variety of sources have described the relation between nodes and leaves to be $2n-1$ where $n$ is the number of leaves. I haven't however been able to find a description of how this relation was derived.

Solution 1:

Any full binary tree can be seen as the structure of a single elimination tournament with $n$ teams corresponding to the leaves. Each non-leaf is a game in which the loser goes home and the winner goes up to the next round. There is one final champion, who wins the root game, and so there must be $(n-1)$ non-leaf nodes since every other team loses exactly once. Hence $n + (n-1) = 2n-1$ nodes altogether.

Solution 2:

A perfect (complete and full) binary tree always has $2^m$ leaves for some $m$. Now how many nodes will it have? Well, it will have $1$ root, and $2$ children of the root, and $4$ total children of those children, and so on, up to and including the $2^m$ leaves. So there will be $$ 1 + 2 + 4 + 8 + \cdots + 2^m = \sum_{i = 0}^m 2^i $$ total nodes in a perfect binary tree with $2^m$ leaves. Now there is a standard formula that $$ \sum_{i = 0}^m 2^i = 2^{m+1} - 1. $$ If we start by saying that $n = 2^m$ is the number of leaves then $2^{m+1} -1$ nodes is the same as $2\cdot 2^m - 1 = 2n - 1$ nodes, which is the formula requested in the question.

Solution 3:

Well start off with the parent node. If you only have one node, that's one leaf, and $2(1) - 1 = 1$. This equation implies that every time you add another leaf, then the total number of nodes will increase by 2.

Now adding two children means taking away one leaf (the parent used to be a leaf) and adding two new leaves, which gives a total of one new leaf. You are adding two nodes from one extra leaf, so it turns out this equation works out.

Solution 4:

A graph follows a basic property

$$\text{Sum of degrees of all nodes }= 2 \times\text{number of edges}$$

Now since it is complete binary tree it follows:

1. Leaves are the only nodes with degree $1$; let there be $n$ of them
2. Root is the only node with degree $2$, there is $1$ root
3. All internal nodes have degree $3$; let there be $x$ of them

Since tree is also a graph so using the basic property you get

$$n\times 1 + 1\times2 + x\times3 = 2 \times\text{number of edges}$$

To compute the number of edges:

Consider every node except root node, it has exactly one parent edge and every edge is some parent edge. So total number of edges is the number of parent edges which is equal to the number of nodes that have a parent i.e. $n+x$ (root node has no parent)

Hence the equation becomes $$n + 2 + 3x = 2\times(n+x)$$ Whence \begin{align}x = n-2\\ \text{Total number of nodes} &= n + 1 + x &+1\text{ is for root node}\\ &= n + 1 + n-2 = 2n-1\end{align}