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.

  • $\begingroup$ In the title of the question, I think you meant to say that T is a non-empty full binary tree? $\endgroup$ – Chameleon Feb 6 '17 at 20:10
  • $\begingroup$ 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. $\endgroup$ – Chameleon Feb 6 '17 at 20:25
  • $\begingroup$ Yeah thanks fixed it @Chameleon $\endgroup$ – John James Feb 6 '17 at 22:53
  • $\begingroup$ 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). $\endgroup$ – Did Feb 6 '17 at 23:21

Your Answer

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

Browse other questions tagged or ask your own question.