Prove If T is a non-empty full binary tree, the number of leaves is $L = I + 1$.

So as the title says I want to prove the above using induction.

Let T be a nonempty, full binary tree then we have a full binary tree with $L=I+1$. We will show that the above will still be valid if we add $2$ nodes pointing to $2$ new vertices in every existing leaf.

By doing the above change:

i) we remove a leaf, as to become an internal node.

ii) we add a new internal node.

iii) we add two new leafs.

• Number of leafs = (number of old leafs) $-1 +2$

• Number of internal vertices= (number of old internal nodes) $+1$

The above will apply every time for all the new leafs of the old tree. If we do that for n leafs, it will increase by n the number of 2 leafs over the number of the nodes.

So now we have $L+n =I+n+1 \to L = I+1$. Proved.

Is my process of thought correct?

Thank you.

• In the title of the question, I think you meant to say that T is a non-empty full binary tree? – Chameleon Feb 6 '17 at 20:10
• Also, just to make your induction process clearer, mention what is the variable you are inducting on, which in your case, appears to be the depth of the binary tree. – Chameleon Feb 6 '17 at 20:25
• Yeah thanks fixed it @Chameleon – John James Feb 6 '17 at 22:53
• The result is true and more interesting for binary trees that are not exactly the n first generations of the complete binary tree (in fact, I suspect this is what you were asked to prove, not the quite reduced version you understood). – Did Feb 6 '17 at 23:21