# Binary trees

• Mar 3rd 2011, 05:42 AM
posix_memalign
Binary trees
This is a task from Kenneth Rosen's "Discrete Mathematics and its applications" book.

How can I use structural induction to show that l(T) (the number of leaves of T) is 1 more than i(T) (the number of internal nodes of T), where T is a full binary tree?

I am completely lost on this one,
I have that the number of leaves is: 2^h, with h being the height of the tree, and obviously 2^h - 1 being the number of internal nodes.

Total number of nodes n = 2^h + 2^h - 1

But I don't see how I should set up the basis step nor the inductive step, or should I use a recursive step?
• Mar 3rd 2011, 01:27 PM
emakarov
Quote:

This is a task from Kenneth Rosen's "Discrete Mathematics and its applications" book.
Mmmm, Rosen...

Structural induction on full binary trees works as follows. Suppose you have a property P of trees, i.e., for each particular tree T, P(T) is either true or false. Suppose further that you prove that P holds on a single-node tree (consisting of a single root), and for any tree as in the picture above, if $P(T_1)$ and $P(T_2)$ hold, then P of the whole tree holds. In this case, P holds on all full binary trees.

The first step is to come up with P. Here it is easy: P(T) is $l(T) = i(T) + 1$. Next, prove P for the single-node tree. For the induction step, suppose $P(T_1)$ and $P(T_2)$ hold, i.e.,

$l(T_1)=i(T_1)+1$ and $l(T_2)=i(T_2)+1$. (*)

Let's call the whole tree T. Express $l(T)$ through $l(T_1)$, $l(T_2)$ and $i(T)$ through $i(T_1)$, $i(T_2)$. Try to prove P(T) from (*).
• Mar 3rd 2011, 01:37 PM
Plato
Are you saying that the graph above is a tree?
But trees are a-cyclic.
• Mar 3rd 2011, 01:52 PM
emakarov
You are right, the graph is not a tree. It's a schematic picture. The triangles represent the subtrees.

Edit: Drew the triangles in dashed lines to distinguish them from the graph edges.
• Mar 4th 2011, 08:18 AM
posix_memalign
Quote:

Originally Posted by emakarov
Mmmm, Rosen...

Structural induction on full binary trees works as follows. Suppose you have a property P of trees, i.e., for each particular tree T, P(T) is either true or false. Suppose further that you prove that P holds on a single-node tree (consisting of a single root), and for any tree as in the picture above, if $P(T_1)$ and $P(T_2)$ hold, then P of the whole tree holds. In this case, P holds on all full binary trees.

The first step is to come up with P. Here it is easy: P(T) is $l(T) = i(T) + 1$. Next, prove P for the single-node tree. For the induction step, suppose $P(T_1)$ and $P(T_2)$ hold, i.e.,

$l(T_1)=i(T_1)+1$ and $l(T_2)=i(T_2)+1$. (*)

Let's call the whole tree T. Express $l(T)$ through $l(T_1)$, $l(T_2)$ and $i(T)$ through $i(T_1)$, $i(T_2)$. Try to prove P(T) from (*).

Basis step:

P(single node): $l(single node) = i(single node) + 1 \Longrightarrow 1 = 0 + 1$

Inductive step:

P(T) : $l(T) = i(T) + 1$
P(T) : $l(T_1) + l(T_2) = i(T) + 1$ (by recursive formula of l(T) )
P(T) : $l(T_1) + l(T_2) = i(T_1) + i(T_2) + 1 + 1$ (by recursive formula of i(T) )

Is this correct at all? What more do I need to complete the proof?
• Mar 4th 2011, 08:43 AM
emakarov
I think you got the idea. I'll be a bit pedantic below.

Quote:

Originally Posted by posix_memalign
Basis step:

P(single node): $l(single node) = i(single node) + 1 \Longrightarrow 1 = 0 + 1$

The left-hand side is what you need to prove. You can't conclude anything from it ( $\Longrightarrow$) because you have not proved it yet. I would write: $l(\bullet)=1, i(\bullet)=0\Longrightarrow l(\bullet)=i(\bullet)+1$.

Quote:

Inductive step:

P(T) : $l(T) = i(T) + 1$
P(T) : $l(T_1) + l(T_2) = i(T) + 1$ (by recursive formula of l(T) )
P(T) : $l(T_1) + l(T_2) = i(T_1) + i(T_2) + 1 + 1$ (by recursive formula of i(T) )
First, the relationship between these three lines is not clear. Is it what you need to prove? Is it the induction hypothesis? Does the first line imply the second or vice versa?

Also, instead of "P(T) : $l(T) = i(T) + 1$", it is better to write "P(T) is $l(T) = i(T) + 1$" or "P(T) means $l(T) = i(T) + 1$" or "P(T) iff $l(T) = i(T) + 1$".

Generally, for each statement you write, it should be clear where it follows from or whether you plan to prove it. So, I would write

By induction hypothesis,

$l(T_1)=i(T_1)+1$ and $l(T_2)=i(T_2)+1$. (1)

Also, from the picture we know that

$l(T)=l(T_1)+l(T_2)$ (2)

and

$i(T)=i(T_1)+i(T_2)+1$. (3)

Therefore,

\begin{aligned}
l(T)&=l(T_1) + l(T_2) &&\mbox{by (2)}\\
&= i(T_1)+1+i(T_2)+1 &&\mbox{by (1)}\\
&= i(T)+1 &&\mbox{by (3)}
\end{aligned}