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

Question

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.

Answer 1

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.

Answer 2

First, it might help to be a little more specific with your terminology. I'll assume you mean "complete" in the way that [CLRS01] defines it:

All leaves have the same depth and all internal nodes have degree 2.

Second, is this homework?

You can prove this using structural induction. Show your claim holds for a "base" tree and then think about how other complete binary trees are built up from these.

As you build larger trees in this fashion, how does the total number of nodes increase? How does the number of leaves increase?

Hint:

Does $\lceil n+1 \rceil = 2 \lceil n/2 \rceil$ ?