[Math] Prove Complete Binary Tree using Induction

discrete mathematicsinduction

Recursive Definitions for Full Binary Tree

The height of a full binary tree, written h(T), is dened recursively as follows.

h(T) = 0

h(T1 T2) = 1 + max(h(T1); h(T2))

The number of nodes in a full binary tree, written n(T), is dened recursively
as follows.

n(T) = 1

n(T1 T2) = 1 + n(T1) + n(T2)

The number of leaves of a full binary tree, written l(T), is dened recursively
as follows.

l(T) = 1

l(T1 T2) = l(T1) + l(T2)

The number of internal nodes in a full binary tree, written i(T), is defined
by the following recursive equations.

i(T) = 0

i(T1 T2) = 1 + i(T1) + i(T2)

Finally Recursive Definition for Complete Binary Tree

A complete binary tree is a full binary tree in which every leaf is at the same level. The set of complete binary trees is defined recursively by:

Basis step: A single vertex is a complete binary tree.

Recursive step: A complete binary tree T= T1 * T2 consists of a new root r together with edges connecting the r to each of the roots, r1 and r2, of two complete binary trees, T1(the left subtree and T2 (the right subtree), respectively, where T1 and T2 have the same height.

NOTE: Complete Binary Tree is a subset of Full Binary Tree

Prove l(T) = 2h(T) in a complete binary tree using Induction

This is my work so far,I have to prove only using above recursive definitions please help me thank you

Let P(n): l(T) = 2h(T), where T is a tree generated by m apps of the Recursive definition(rd) of the recursive step(rs) of complete binary tree.

Basis Step: P(0): l(T) = 1

2.h(T) = 0

  1. 1 = 20

4.1 = 1

P(0) is True

IH: Assume p(k) is true for k >= 1

p(k): l(T) = 2h(T), where T is a tree generated by k apps of the Recursive definition(rd) of the recursive step(rs) of complete binary tree k >= 1

Inductive Step:

Assume p(k+1): l(T) = 2h(T), where T is a tree generated by k+1 apps of the Recursive definition(rd) of the recursive step(rs) of complete binary tree

Proof

  1. Assume T is created by k+1 apps of rs of rd of Complete Binary Tree, then T = (T1 * T2)

  2. Then l(T) = l(T1) + l(T2) by the rs rd of l(T)

    3.l(T) = 2h(T1) + 2h(T2) by IH

  3. Stuck Here I have to make it equal l(T) = 2h(T)

Best Answer

$$l(T)=l(T_1T_2)=l(T_1)+l(T_2)=2^{h(T_1)}+2^{h(T_2)}=2\cdot 2^{h(T_1)}=2^{1+h(T_1)}=2^{h(T)}.$$

The first and second equality are definition, the third equality is the IH, the fourth equality uses that $h(T_1)=h(T_2)$ by definition, the fifth equality is clear, the sixth equality is definition plus, again, $h(T_1)=h(T_2)$.

Related Question