Problem Detail: Given a complete binary tree with $n$ nodes. I’m trying to prove that a complete binary tree has exactly $lceil n/2 rceil$ leaves. I think I can do this by induction. For $h(t)=0$, the tree is empty. So there are no leaves and the claim holds for an empty tree. For $h(t)=1$, the tree has 1 node, that also is a leaf, so the claim holds. Here I’m stuck, I don’t know what to choose as induction hypothesis and how to do the induction step.
Asked By : Luc Peetersen
Answered By : JeffE
If the statement you’re trying to prove by induction is
For all positive integers $n$, a complete binary tree with $n$ nodes has $lceil{n/2}rceil$ leaves.
then the induction hypothesis must be
For all positive integers $k<n$, a complete binary tree with $k$ nodes has $lceil{k/2}rceil$ leaves.
Similarly, if the statement you’re trying to prove by induction is
For all positive integers $n$, a hoosegow with $n$ whatsits has $2^{lfloorsqrt{n}rceil!}cdot n^pi$ nubbleframets.
then the induction hypothesis must be
For all positive integers $k<n$, a hoosegow with $k$ whatsits has $2^{lfloorsqrt{k}rceil!}cdot k^pi$ nubbleframets.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2193
