4
$\begingroup$

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.

$\endgroup$

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
    $\begingroup$ see cs.stackexchange.com/questions/805/… $\endgroup$ – Zach Langley Jun 1 '12 at 21:59
  • $\begingroup$ That's for any binary tree. I need to prove that a complete binary tree has exactly ⌈n/2⌉ leaves. $\endgroup$ – Luc Peetersen Jun 1 '12 at 22:07
  • 2
    $\begingroup$ Use induction on $t$. $\endgroup$ – Yuval Filmus Jun 1 '12 at 22:13
  • $\begingroup$ 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$. $\endgroup$ – Joe Jun 2 '12 at 4:04
  • $\begingroup$ @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. $\endgroup$ – Raphael Jun 2 '12 at 9:43
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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