Inductive proof of binary tree child nodes

Question

How can I prove that the number of interval nodes in a binary tree with n leaves (where each interval node has two children) is n-1, using induction?

Answer 1

The outline of a proof by induction is thus:

1. Prove that P(1) is true. In this case, it's trivial to prove that a binary tree with one node has exactly one leaf node and zero internal nodes.

2. Prove that P(n) implies P(n + 1). This I'll leave up to you (because it's your homework :P), but think about what happens when you add two children to an existing leaf node and it'll be obvious how it works.

Answer 2

An alternative to the

P(n) => P(n + 1)

form of the inductive step is the equivalent form of

\forall n < N . P(n) => P(N)

(Read "if P(n) holds for each n less than N, than it also holds for N". You might want to try proving the equivalance of the two forms.)

With the latter approach, it becomes possible to start the second part of the proof something like the following:

Suppose it has been proven that all binary trees having n leaves, where n < N, have n - 1 internal nodes. Consider a binary tree with N leaves.

Now you need to apply the assumption to the task of calculating the numbers of leaves and internal nodes in the N-leaf tree under consideration; I'll leave this part to you.