Prove that a full binary tree has $\frac{N+1}{2}$ leaves

Question

$N$ is the total number of nodes. It is to prove that the number of leaves equals $\frac{N+1}{2}$

I guess this can be proven by induction. The smallest full binary tree is $N=1$ with $\frac{1+1}{2} = 1$ leave. I further guess that the induction hypothesis must deal with the fact that the formula above is valid for subtrees. Obviously the number of nodes of a full binary tree must be odd. But I think this is statement you can't take for true without proof.

Induction hypothesis:

$$L(k)=\frac{k+1}{2}$$ where $k<N$ and $k=2i+1$ with $i\in\mathbb{N_0}$

Induction step:

$$L(i) = \frac{2i+1+1}{2}=\frac{2i+2}{2}=i+1$$ $$L(i+1) = L(i) + 1$$ $$L(i+1) = i + 1+1=i+2=\frac{k-1}{2}+2=\frac{k+3}{2}$$

But that doesn't make sense. I am happy about any hint.

Edit: Solution:

$$N_d=1+\sum_{i=2}^{d}(2r_{i-1})$$ $$N_{d+1}=1+\sum_{i=2}^{d}(2r_{i-1})+2r_d$$ $$L_{d+1}=L_d+r_d$$ $$L_{d+1}=\frac{N_d+1}{2}+r_d=\frac{1+\sum_{i=2}^{d}(2r_{i-1})+1}{2}+r_d=\frac{1+\sum_{i=2}^{d}(2r_{i-1})+1+2r_d}{2}=\frac{N_{d+1}+1}{2}$$

Answer 1

This answer is a solution for full binary trees

Use induction by the number of nodes $N$. For $N=1$ it's clear, so assume that all full binary trees with $n\leq N$ nodes have $L_n = \frac{n+1}{2}$ leaves (induction hypothesis). Let's take an arbitrary full tree with $N+1$ nodes. As $N\geq 1$ we will have at least $2$ leaves. Choose one pair of leaves of the same depth with the same parent and remove them.

We get a new tree with $n=N-1< N$ nodes which is still full (because every node has either two children or none and this condition is not disregarded), so we can use our induction hypothesis, which tells us that this smaller tree has $L_{N-1} = \frac{N-1+1}{2}$ leaves. However, the original tree has exactly one leaf more than the smaller tree (the $2$ children are replaced by $1$ parent), so we have a total of

$$ L_{N+1} = L_{N-1} + 1 = \frac{N}{2} + 1 = \frac{N+2}{2} = \frac{(N+1)+1}{2} $$ leaves, which finishes the induction proof.

Answer 2

HINT: There is exactly 1 vertex of degree 2, the remaining $N-1$ vertices each have either degree 3 or 1. There must be $N-1$ edges total, so letting $A$ be the number of leaves i.e.,equivalently, $A$ is the number of degree-1 vertices, the Handshaking Lemma gives the following equation:

$$2+A+3(N-A-1) = 2N-2.$$

[The sums of the degrees of $T$ must add up to twice the number of edges in $T$.] This implies $A$ must be indeed $\frac{N+1}{2}$. [Notice we don't even need that $T$ is complete, only that every nonleaf vertex save for exactly one nonleaf vertex, has degree 3. This is a property a complete binary tree satisfies, but there are many other binary trees on $N$ vertices that are not complete and still satisfy this as well.]

Answer 3

This answer is a solution for complete and perfect binary trees

You shouldn't do induction by $N$, but induction by the depth of the tree $d$.

The induction start is the same for $N=d=1$. Let's look at the induction step $d\to d+1$: We will not only show the number of leaves by induction but also the number of nodes $N_d$ by induction:

Take a perfect binary tree $B_{d+1}$ of depth $d+1$ with $B_d$ as part of this tree (just the last layer is missing). We know that each leaf of $B_d$ (the tree with depth $d$) transforms into two leaves in the next layer $d+1$. By induction hypothesis $B_d$ has $L_d=\frac{N_d+1}{2}$ leaves and $N_d=2^{d}-1$ nodes (we show this number using induction as well). Now we add $2$ nodes for each leaf and each leaf turns into two leaves. That means that the new number of nodes is

$$ N_{d+1} = N_d + 2L_d =2^d-1 + 2\cdot \frac{N_d+1}{2} =2^d-1+(2^d-1+1) = 2\cdot 2^d-1 = 2^{d+1}-1 $$

and the number of leaves is $$ L_{d+1} = 2L_d =\frac{N_d+1}{2} \cdot 2 = \frac{2^d-1+1}{2}\cdot 2 = \frac{2^{d+1}}{2} = \frac{2^{d+1}-1+1}{2} = \frac{N_{d+1}+1}{2} $$

This finishes the proof.

Edit: You can generalize above result for complete binary trees as well:

In general you have not $N_d=2^d-1$ nodes, but $N_d=2^{d-1}-1+2k$ nodes with $1 \leq k\leq 2^{d-1}$ (in the last layer some pairs of two nodes are added, but at least one pair of nodes is added). As above denote with $B_{d+1}$ the full binary tree of depth $d+1$ (with only $2k$ nodes of depth $d+1$) and with $B_d$ the perfect binary tree that comes from $B_{d+1}$ after removing all nodes of depth $d+1$. We then have the formula ($.^p$ denotes the values for the perfect binary tree): $$N_{d+1} = N_d^p + 2r$$ for $r$ the number of pairs of children ($N_d^p$ from the perfect binary tree) and $$L_{d+1} = L_d^p + r.$$ The $+r$ is derived as follows: $r$ leaves of $B_d$ get two children. That means that we get an additional of $r$ leaves and not an additional of $L_d^p$ leaves as for perfect binary trees.

Using the formulas for perfect binary trees shown in the previous induction yields:

$$N_{d+1} = 2^d-1+2r$$ $$L_{d+1} = \frac{N_d^p+1}{2}+r = \frac{(2^d-1)+1+2r}{2} = \frac{(2^d-1+2r)+1}{2} = \frac{N_{d+1}+1}{2}$$

Thus the formula is correct for full binary trees as well.