Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

migrated from cstheory.stackexchange.com Jun 1 '12 at 21:33

This question came from our site for theoretical computer scientists and researchers in related fields.

2  
    
That's for any binary tree. I need to prove that a complete binary tree has exactly ⌈n/2⌉ leaves. –  Luc Peetersen Jun 1 '12 at 22:07
2  
Use induction on $t$. –  Yuval Filmus Jun 1 '12 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 Jun 2 '12 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. –  Raphael Jun 2 '12 at 9:43

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.