14
$\begingroup$

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.

$\endgroup$
7
  • 3
    $\begingroup$ First, note that we can use LaTeX here. Click "edit" to see how I did it. Secondly, I do not see an induction. You are throwing some numbers around there but there is no proof structure and no relation to heaps at all. Can you improve it? And lastly, the claim is wrong: a sorted list fulfills the heap property and has only one leaf. Have you left out some assumptions? $\endgroup$
    – Raphael
    Commented Mar 26, 2012 at 22:11
  • $\begingroup$ Is @Kaveh's edit what you had in mind, i.e. "at most"? $\endgroup$
    – Raphael
    Commented Mar 26, 2012 at 22:37
  • $\begingroup$ @Raphael, reading the question again, I think it might be about heaps where every internal node has exactly two children (in which case the original question makes sense and the claim is correct, or something similar). $\endgroup$
    – Kaveh
    Commented Mar 26, 2012 at 22:43
  • 1
    $\begingroup$ @Kaveh Ah yes, I see your confusion. The heap's nodes have at most two children (hence the binary-tree tag) $\endgroup$
    – varatis
    Commented Mar 27, 2012 at 3:46
  • 1
    $\begingroup$ I see. With the claim formulated precisely, there is indeed no need for further assumptions. The property holds in fact for all binary trees. $\endgroup$
    – Raphael
    Commented Mar 27, 2012 at 7:05

2 Answers 2

8
$\begingroup$

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.
$\endgroup$
1
  • $\begingroup$ I maybe wrong but isn't a binary tree with height h has $2^{h+1}-1$ nodes due to the fact that in binary numbers, $1111_2=10000_2 -1$? $\endgroup$
    – Andes Lam
    Commented Oct 22, 2022 at 10:40
2
$\begingroup$

I am a little confused by the question. If you are interested in trees with degree at most $3$, which is what Wikipedia says you want, then we run into the problem that a single edge has $n=2$ nodes and $n=2$ leaves, but $n/2 = 1$. Anyway, here is something close that has an easy argument.

Let $T$ be such a tree with $n$ nodes and $L$ leaves. Since $T$ is a tree, there are $n-1$ edges, and double counting them, we see that $$2n - 2 \le L + 3(n - L)$$ which says that $$2L\le n + 2$$ and this is tight in the two-vertex example above. I guess that if you want to assume that there one root of degree two and $n\ge 3$, then you can refine this argument to give $$2L \le n + 1$$ which is what you are looking for, and this is tight when the tree is full.

$\endgroup$
3
  • $\begingroup$ I guess we silently assume rooted trees here; Wikipedia does so, too. $\endgroup$
    – Raphael
    Commented Mar 28, 2012 at 14:18
  • 1
    $\begingroup$ Wikipedia sort of equivocates, saying: "Outside the tree, there is often a reference to the "root" node (the ancestor of all nodes), if it exists." Anyway, this argument seems worth writing down, since it is different and quite easy. $\endgroup$
    – Louis
    Commented Mar 28, 2012 at 14:23
  • $\begingroup$ If you read on, all edges are directed, they talk of "children" and "parents". That does not make sense in unrooted trees. In consequence, a leaf would be a node with outdegree 0. $\endgroup$
    – Raphael
    Commented Mar 28, 2012 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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