0
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Can you please explain the very last part how is that 2^1+h(T1) = 2^h(T) please $\endgroup$ – user149068 Sep 27 '14 at 20:52
  • $\begingroup$ h(T1 T2) = 1 + max(h(T1); h(T2)) and h(T1)=h(T2) for a complete binary tree. $\endgroup$ – mathse Sep 27 '14 at 20:56
  • $\begingroup$ Thank you so much for taking the time to answer I actually got almost to the end just wasnt 100% sure If I was right thanks again! $\endgroup$ – user149068 Sep 27 '14 at 20:57
  • $\begingroup$ You're welcome :) $\endgroup$ – mathse Sep 27 '14 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.