Proving a binary tree has at most $\lceil n/2 \rceil$ leaves

I'm trying to prove that a binary tree with $n$ nodes has at most $\left\lceil \frac{n}{2} \right\rceil$ leaves. How would I go about doing this with induction?

For people who were following in the original question about heaps, it has been moved here.

I assume now that the question is the following:


Given a binary tree with $n$ nodes, prove that it contains at most $\left\lceil \frac{n}{2} \right\rceil$ leaves.

Let us work with the tree definition $\mathrm{Tree}= \mathrm{Empty}\mid \mathrm{Leaf} \mid \mathrm{Node}(\mathrm{Tree},\mathrm{Tree})$. For $T$ such a tree, let $n_T$ the number of nodes in $T$ and $l_T$ the number of leaves in $T$.

You are correct to do this by induction, but you will need structural induction that follows the tree structure. For trees, this is often done as complete induction over the height $h(T)$ of the trees.

The induction anchor has two parts. First, for $h(t)=0$ we have $T=\mathrm{Empty}$ with $l_T=n_T=0$; the claim clearly holds for the empty tree. For $h(t)=1$, i.e. $T = \mathrm{Leaf}$, we similarly have $l_T=1=\left\lceil \frac{n_T}{2} \right\rceil$, so the claim holds for leaves.

The induction hypothesis is: Assume that the claim holds for all (binary) trees $T$ with $h(T)\leq k$, $k\geq 1$ arbitrary but fixed.

For the inductive step, consider an arbitrary binary tree $T$ with $h(T)=k+1$. As $k\geq 1$, $T=\mathrm{Node}(L,R)$ and $n_T = n_L+ n_R+1$. As $L$ and $R$ are also binary trees (otherwise $T$ would not be) and $h(L),h(R)\leq k$, the induction hypothesis applies and have

$\qquad \displaystyle l_L \leq \left\lceil \frac{n_L}{2} \right\rceil \text{ and } l_R \leq \left\lceil \frac{n_R}{2} \right\rceil.$

As all leaves of $T$ are either in $L$ or $R$, we have that

$\qquad \begin{align*}
l_T &= l_L + l_R \\
&\leq \left\lceil \frac{n_L}{2} \right\rceil + \left\lceil \frac{n_R}{2} \right\rceil \\
&\leq \left\lceil \frac{n_L + n_R + 1}{2} \right\rceil \qquad (*)\\
&= \left\lceil \frac{n_T}{2} \right\rceil
\end{align*}$

The inequality marked with $(*)$ can be checked by (four way) case distinction over whether $n_L,n_R\in 2\mathbb{N}$. By the power of induction, this concludes the proof.

As an exercise, you can use the same technique to prove the following statements:

• Every perfect binary tree of height $h$ has $2^h-1$ nodes.

• Every full binary tree has an odd number of nodes.

StackExchange Computer Science Q#805, answer score: 8