Binary trees

**posix_memalign** · March 3rd 2011, 04:42 AM

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?

**emakarov** · March 3rd 2011, 12:27 PM

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 (*).

**Plato** · March 3rd 2011, 12:37 PM

Are you saying that the graph above is a tree?
But trees are a-cyclic.

**emakarov** · March 3rd 2011, 12:52 PM

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.

**posix_memalign** · March 4th 2011, 07:18 AM

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?

**emakarov** · March 4th 2011, 07:43 AM

I think you got the idea. I'll be a bit pedantic below.

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$ .

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}<br /> l(T)&=l(T_1) + l(T_2) &&\mbox{by (2)}\\<br /> &= i(T_1)+1+i(T_2)+1 &&\mbox{by (1)}\\<br /> &= i(T)+1 &&\mbox{by (3)}<br /> \end{aligned}$

Thread: Binary trees

LinkBack

Thread Tools

Display

Binary trees

Similar Math Help Forum Discussions

The number of possible binary trees with n nodes

Binary Trees

Binary Trees

how can you plant 10 trees in 5 rows of 4 trees each?

binary trees

Search Tags