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

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.

• Commented Jun 1, 2012 at 21:59
• That's for any binary tree. I need to prove that a complete binary tree has exactly ⌈n/2⌉ leaves. Commented Jun 1, 2012 at 22:07
• Use induction on $t$. Commented Jun 1, 2012 at 22:13
• You come up with the inductive hypothesis using the same method you would for any other inductive proof. You have a base case for $h(t) = 0$ and $h(t) = 1$. You want to show that it's true for all values of $h(t)$, so suppose that it's true for $h(t) = k$ (inductive hypothesis) and use that to show that it's true for $h(t) = k + 1$.
– Joe
Commented Jun 2, 2012 at 4:04
• @LucPeetersen: The technique my answer uses directly applies. It is independent of the specific statement. You should be able to adapt the proof there to work for your problem. Tempted to close as duplicate, but let's wait what others say. Commented Jun 2, 2012 at 9:43

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.

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$ ?