How can I prove that a complete binary tree has $\lceil n/2 \rceil$ leaves?

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^{\lfloor\sqrt{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^{\lfloor\sqrt{k}\rceil!}\cdot k^\pi$ nubbleframets.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2193