Observation on Binary Trees

In this post I will proof the following observation:

Let \(T\) be a binary tree, \(I\) the number of internal nodes and \(L\) the number of leaves in \(T\) then

\[
L = I + 1
\]

We will proof this fact by observing the following. Every binary tree can be "grown" by replacing leaves with trivial binary tree.

Assume to the contrary that not every binary tree can be grown by replacing leaves with trivial binary trees. Then there must exist a smallest binary tree which can not be grown in such a way. Call it \(C\).
Notice that both subtrees of \(C\) are smaller binary trees. Because \(C\) was the smallest tree which could not be grown, both subtrees can be grown.
But the following description grows \(C\).

1. Take trivial binary tree
2. On the left leaf use the description for the left subtree of \(C\)
3. On the right leaf use the description for the right subtree of \(C\)

This contradicts the fact that \(C\) was the smallest such tree. We are forced to drop the assumption that there exist a binary tree which could not be grown. Therefore all binary trees can be grown.

Now for the trivial binary tree is is clear that

\[
L = I + 1
\]

And when a leaf is grown both \(L\) and \(I\) go up by 1, maintaining the equality. From the above observations one can conclude that the equations hold for all binary trees.