= Null child slot count
{title2=$n+1$}
Every nonempty finite <binary tree> with $n$ <vertices> has exactly $n+1$ empty <binary tree child slots>. There are $2n$ slots altogether, and precisely $n-1$ occupied slots, one for each <edge> of its underlying <tree>. Therefore
$$
2n-(n-1)=n+1.
$$
This counts missing child references, not <vertices> or leaves. In the mixed four-<vertex> example, $A$ has no empty <binary tree child slots>, $B$ has one, and $C,D$ each have two: $0+1+2+2=5$. The four-<vertex> chain also has five: one at each of its first three <vertices> and two at the last. For $n=0$, there are no <vertices> and hence no child fields; the empty <binary tree> instead has a single empty root position if it is represented by a root reference.
A second proof uses the recursive decomposition. Count every empty <subtree> occurrence, including the root position for the empty <binary tree>: let $e(\varnothing)=1$. For a nonempty <binary tree>, $e(T)=e(L)+e(R)$. If the two <subtrees> have $n_L,n_R$ <vertices>, <structural induction> gives $e(T)=(n_L+1)+(n_R+1)=n+1$. Distinct empty positions may share the same `null` value; these are occurrences, not separately allocated objects. This count is useful when analysing the base cases reached by a <structural recursion> that calls both <subtrees> of every <vertex>.
Back to article page
