Question

Use structural induction to show that I(T) , the number of leaves of a full binary tree T , is 1 more than i (T) , the number of internal vertices of T .

Short answer

Prove that the number of leaves of a full binary tree T is 1 more than the number of internal vertices of T.

Step-by-step solution

Step 1:Introduction

Structural induction is used to prove that some proposition P(x) holds for all x of some sort of recursively defined structure, such as formulas, lists, or trees. A well-founded partial order is defined on the structures ("subformula" for formulas, "sublist" for lists, and "subtree" for trees).

Step 2:Solution

The objective is to use structural induction to show that t(T) , the number of leaves of a full binary trees T is more than i(T) , the number of internal vertices ofT.

Let the number of leaves of a full binary tree T be t(T) .

Let the number of internal vertices of T be i (T) .

We shall show that t(T) = 1 + i (T) , using structural induction.

Induction Step

Basis step:

Consider the tree consisting of a single vertex, say p.

Thus, there is no internal vertices and has leaf.

Therefore,

t(p) = 1 + i (p)

Recursive Step:

Let $T_1$as its left sub tree and $T_2$as its right sub tree and $T_2$ .

We show that if the result is true for the trees $T_1$and $T_2$, then it is true for tree .

Now,

$\begin{array}{r}t\left(T_1\right)=i\left(T_1\right)+1\\ t\left(T_2\right)=i\left(T_2\right)+1\end{array}$

The set of leaves of the tree $T=T_1{T}_2$is the union of the sets of eaves of $T_1$and $T_2$.

Thus, for the full binary tree $T=T_1{T}_2$,

$ı\left(T_1\cdot T_2\right)=i\left(T_1\right)+i\left(T_2\right)+1$

Add, the number of leaves,

$\begin{array}{r}t\left(T_1\cdot T_2\right)=t\left(T_1\right)+t\left(T_2\right)\\ t\left(T\right)=i\left(T_1\right)+1+i\left(T_2\right)+1\\ =t\left(T_1{T}_2\right)+1\\ =i\left(T\right)+1\\ t\left(T_2\right)=i\left(T_2\right)+1\\ T=T_1{T}_2\\ \end{array}$

Hence prove that the number of leaves of a full binary tree T is 1 more than the number of internal vertices of T .