Proving the Number of Leaves is One More Than Internal Nodes in Binary Trees

[Jairo Rojas]

Homework Statement

In a binary tree all nodes are either internal or they are leaves. In our definition, internal nodes always have two children and leaves have zero children. Prove that for such trees, the number of leaves is always one more than the number of internal nodes.

Homework Equations

The Attempt at a Solution

Proof by induction

Base case:
n=1
Number of leafs=1
External nodes=0

Induction step: Assume a binary tree has k internal nodes and k+1 leaves. Therefore we have to show that a binary tree with k+1 internal nodes will have (k+1)+1 leaves

If we want to increase the number of external nodes by 1 in this binary tree, we would have to make a leaf an internal node and we do this by sticking two new leaves to an old leaf. Doing this the net change in leaves is 1 because we eliminate 1 and add 2 new. So the number of external nodes is k+1 and the number of leaves is (k+1)+1. Consequently, by induction, the number of leaves is always one more than the number of internal nodes in a binary tree.

Is that correct?

 

[andrewkirk]

Is that correct?

That's certainly the idea of the induction proof. But that's too informal a way to write it, unless you have a very easygoing lecturer. A more formal approach would be as follows:

Start with a proposition P(n) which states that all binary trees with n leaves have n-1 internal nodes.
The base case is P(1), which is trivial, and you have covered that above.
For the induction step, you need to prove that, if P(n) is true for all n in 1,...,m, then P(m+1) is also true.

This involves a similar approach to what you have above, except that you need to work backwards from a tree with m+1 leaves to one with m leaves, rather than forwards as you did above.

If you can prove that induction step then, by the principle of induction, it is proven that P(n) is true for all natural numbers n.

See how you go.