Proof by induction of missing nodes of binary tree

Question

I am trying to prove that the number of missing children of a binary tree T in terms of N (number of nodes) is N+1

• I can get the basis step:
• Minimum number of nodes in a binary tree is 1 (root). For N=1 ==> N+1=1+1=2

This is correct since a lone root node has two missing children. However I am having trouble deducing the inductive hypothesis that will give me N+1

Answer 1

Assume that an empty tree ($0$ nodes) has $1$ missing child (the root node). Take this to be the base case.

Given a tree $T$ with $n \geq 1$ nodes, observe that it decomposes into three parts:

• The root node.
• The subtree $T_L$ rooted at the root node's left child (assume it has $\ell \geq 0$ nodes).
• The subtree $T_R$ rooted at the root node's right child (assume it has $r \geq 0$ nodes).

where $n = \ell + r + 1$. Observe that the number of missing children in $T$ is precisely the sum of the missing children in $T_L$ plus $T_R$. But since both subtrees have less than $n$ nodes, it follows by the induction hypothesis that the total number of missing children is: $$ (\ell + 1) + (r + 1) = (\ell + r + 1) + 1 = n + 1 $$ as desired.