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$
  • 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 Mar 26 '12 at 22:11
  • $\begingroup$ Is @Kaveh's edit what you had in mind, i.e. "at most"? $\endgroup$ – Raphael Mar 26 '12 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 Mar 26 '12 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 Mar 27 '12 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 Mar 27 '12 at 7:05
7
$\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$
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$
  • $\begingroup$ I guess we silently assume rooted trees here; Wikipedia does so, too. $\endgroup$ – Raphael Mar 28 '12 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 Mar 28 '12 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 Mar 28 '12 at 14:25

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.