0
$\begingroup$

I need to proof by induction that at full binary tree there are $\frac{n+1}{2}$ leafs if $|V|=n$.

So, I won't write you the whole proof, just my idea, and I'd like to know if this OK...

So we assume the at full binary tree there is $\frac{n+1}{2}$ leafs for a specific $n$.
We have to prove that the assume is correct for tree with $k=n+2$ vertices.

How we proving it?
We will take a tree with $n$ vertices, we know that the induction assumption is good for this tree.
Then we will take one leaf and add him 2 vertices.

So, we have a tree with $\frac{n+2-1}{2}$ leafs (because, we add 2 leafs so there is $n+2$ vertices, and we lose 1 leaf because wee add to him two children, but we get 2 leafs).

And then we get what we want to prove...

I'm right? If not - Where is my mistake?

Thank you!

$\endgroup$
2
  • $\begingroup$ Mauro, that may be true if the proof is just considering complete trees but if you are considering the broader class of trees where every node has 0 or 2 children, that argument doesn't work. I took "full binary trees" to mean this latter class, although I could be wrong. $\endgroup$ Commented Oct 31, 2014 at 15:23
  • $\begingroup$ According to Wikipedia, what I thought. $\endgroup$ Commented Oct 31, 2014 at 15:28

1 Answer 1

Reset to default
2
$\begingroup$

You have a mistake. If you are proving by induction on $n$, your induction hypothesis is that all trees of size $n$ have $\frac{n+1}{2}$ leaves and you must prove from this hypothesis that all trees of size $n+2$ have $\frac{(n+2)+1}{2}$ leaves. The step that you're missing is showing that all trees of size $n+2$ are extensions of trees of size $n$ - otherwise there might be some rogue tree of size $n+2$ that your argument never addressed.

If on the other hand you want to prove that if a given tree with $n$ vertices has $\frac{n+1}{2}$ leaves then a tree extending that tree with $n+2$ vertices has $\frac{(n+2)+1}{2}$ nodes, you are using a form of induction called structural induction. I am not sure whether you are allowed to use this technique.

$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.