Use structural induction to prove that the height, h(T), of a complete binary tr

Question

Use structural induction to prove that the height, h(T), of a complete binary tree T with L(T) leaves is h(T) = log2L(T)

I have completed the basis step already. This is where I am stuck at.

Inductive Hypothesis: Assume P(k) is true for an arbitrary non-negative integer k and P(k) is the statement "the height, h(T), of a complete binary tree T with L(T) leaves is h(T) = log2L(T)" where T is generated in k or fewer applications of the recursive step of the recursive definition of complete binary trees.

Inductive Step: Let P(k+1) be the statement "the height, h(T), of a complete binary tree T with L(T) leaves is h(T) = log2L(T)" where T is generated in k+1 or fewer applications of the recursive step of the recursive definition of complete binary trees.

We know that h(T) = max(h(T1), h(T2)) + 1 and L(T) = L(T1) + L(T2) where T = T1*T2. Since T is a complete binary tree, h(T1) = h(T2) and L(T1) = L(T2)

L(T) = 2h(T) for complete binary trees.

knowing this we can conclude that h(T) = log2L(T)

Stuck here. I am not sure how to show that h(T) = log2L(T)

Explanation / Answer

L(T) = 2h(T)

taking log on both sides

log2L(T) = log2 2h(T)

h(T) = log2L(T)

its a simple log formula

logaax = x

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.