# Proof by induction and height of a binary tree

I need some help with a simple proof. I want to know if this proof is correct:

Let's define the height of a binary tree node as:

• 0, if the node is a leaf
• 1 + the maximum height of the children

The height of the tree is the height of the root. I have to prove by induction (for the height k) that in a perfect binary tree with n nodes, the number of nodes of height k is:

$$\left\lceil \frac{n}{2^{k+1}} \right\rceil$$

Solution:

(1) The number of nodes of level c is half the number of nodes of level c+1 (the tree is a perfect binary tree).

(2) Theorem: The number of leaves in a perfect binary tree is $\frac{n+1}{2}$

Basis: For $k=0$ we have: $$\left\lceil \frac{n}{2} \right\rceil$$ Because the tree is perfect binary tree, n is odd, so:

$$\left\lceil \frac{n}{2} \right\rceil = \frac{n+1}{2}$$

That is true because of the theorem (2).

Hypothesis:

Let's suppose that the statement is true for $k = m$, let's prove it for $m+1$

We have:

$$\left\lceil \frac{n}{2^{m+2}} \right\rceil = \left\lceil \frac{\frac{n}{2^{m+1}}}{2} \right\rceil$$

The number of nodes of height $m+2$ is half the number of nodes of height $m+1$ that is true because of (1)

Is it ok? Can I use the statement (2) to prove it or is not formally correct?

-
The plural of "child" is "children"! –  Olivier Bégassat Jan 15 '13 at 15:11
@OlivierBégassat sorry :P –  Antonio Jan 15 '13 at 15:15

Let me make certain I understand you correctly, since you're using some terminology that's different from what I'm used to. (I'm used to roots of height $0$, and level and height of a node coinciding, but that clearly isn't the case for you.) It seems to me that if you're dealing with a tree of height $j$, then a node will be on level $c$ if and only if said node has height $j-c$. Is this accurate?

(As a side note, we require $k$ to be no greater than the height of the tree for the formula to work.)

Operating under the assumption that I am correctly interpreting you (until and unless you inform me otherwise), let me now talk about your proof. Your basis case is just fine. In the hypothesis case, you've correctly concluded from (1) that there are half as many nodes of height $m+2$ as there are of height $m+1$--however, this is not useful for the induction. Instead, we need to relate the number of nodes of height $m+1$--about which we would like to draw a conclusion--to the number of nodes of height $m$--about which we made the inductive hypothesis.

I suspect that what you actually meant was that there are half as many nodes of height $m+1$ as there are of height $m$. This is the correct observation to make, so long as $m$ is less than the height of the tree (which I take to be a hidden assumption). By inductive hypothesis, there are $$\left\lceil\frac{n}{2^{m+1}}\right\rceil$$ nodes of height $m$, and so by our observation, there are $$\frac12\cdot\left\lceil\frac{n}{2^{m+1}}\right\rceil$$ nodes of height $m+1$. Your task, then, is to show that $$\frac12\cdot\left\lceil\frac{n}{2^{m+1}}\right\rceil=\left\lceil\frac{n}{2^{m+2}}\right\rceil,$$ or equivalently, $$\left\lceil\frac{n}{2^{m+1}}\right\rceil=2\cdot\left\lceil\frac{n}{2^{m+2}}\right\rceil.\tag{&}$$

By definition, for any real $x$, $\lceil x\rceil$ is the least integer not less than $x$. Thus, we have $$\frac{n}{2^{m+1}}\le\left\lceil\frac{n}{2^{m+1}}\right\rceil<\frac{n}{2^{m+1}}+1\tag{#}$$ and $$\frac{n}{2^{m+2}}\le\left\lceil\frac{n}{2^{m+2}}\right\rceil<\frac{n}{2^{m+2}}+1.\tag{##}$$ Multiplying everything by $2$ in $(\#\#)$, we find that $$\frac{n}{2^{m+1}}\le 2\cdot\left\lceil\frac{n}{2^{m+2}}\right\rceil<\frac{n}{2^{m+1}}+2,$$ so by $(\#)$ there are only two possibilities to consider:

(a) $\left\lceil\frac{n}{2^{m+1}}\right\rceil=2\cdot\left\lceil\frac{n}{2^{m+2}}\right\rceil$,

(b) $\left\lceil\frac{n}{2^{m+1}}\right\rceil=2\cdot\left\lceil\frac{n}{2^{m+2}}\right\rceil+1$.

In any complete balanced binary tree, there are an even number of nodes on all but the $0$th level--a consequence of (1). Hence, since we assumed that $m$ was less than the height of the tree (so nodes of height $m$ are not on the $0$th level) and that $\left\lceil\frac{n}{2^{m+1}}\right\rceil$ is the number of nodes of height $m$, option (a) is the correct one, so $(\&)$ holds, as desired.

-
Thanks Cameron. I'm used to roots of height etc (like you). This exercise just use a different definition for height of a tree. Your assumption is correct. I'm just studying your answer. I'll let you know asap. Thanks again –  Antonio Jan 15 '13 at 19:02
"I suspect that what you actually meant was..." Yes, of course, sorry. The answer is very straightforward. Also "(1) follows from (2)" is a good point. Thank you very much. –  Antonio Jan 15 '13 at 20:15

As long as you have proved theorem $(2)$ independently, there is no problem with using it. But your induction step and statement $(1)$ are slightly incorrect. Consider $n=6$ for example. It has $3$ nodes of height $0$ and $2$ of height $1$. Correct statement there would be that if $f(c)$ is number of nodes of height $c$, then $f(c+1) = \lceil \frac{f(c)}{2}\rceil$.

-
I'm talking about full binary tree, it must be complete and balanced. With n=6 we cannot create a balanced tree. Thanks for the other informations –  Antonio Jan 15 '13 at 18:49
Statement (1) actually follows inductively from statement (2), as "plucking the leaves" from a complete balanced binary tree (with more than one node) gives us yet another complete balanced binary tree, and the levels of the smaller tree coincide precisely with the same-numbered levels of the larger tree. From this, we can conclude that complete balanced binary trees of height $j$ must have $n=2^{j+1}-1$ nodes (which is why $n=6$ isn't viable), and for each $0\le k\le j$, the $k$th level has $2^k$ nodes. –  Cameron Buie Jan 15 '13 at 18:56
@CameronBuie: The term complete balanced tree is slightly ambiguous. It is usually used to state that all levels (by levels here, I mean distance from the root) are full, except possibly the last level. But it also also used sometimes to state that all levels are full, including the last one. If we use this latter definition, you are forcing $n=2^r-1$ for some $r$ and the given statement follows trivially as there are exactly $2^{r-k-1}$ nodes at height $k$. But the given statement is true even with the former definition. –  polkjh Jan 15 '13 at 19:14
@polkjh Thanks for the clarification. Maybe is better to use "perfect binary tree" (wikipedia)? –  Antonio Jan 15 '13 at 19:18
Fair point (looking at wikipedia shows that the terms for types of trees are terribly ambiguous). Still, your example $n=6$ also provides a counterexample to theorem (2), so contextually, the former definition of complete balanced tree cannot be the one being used, here. –  Cameron Buie Jan 15 '13 at 19:22