Binary tree child slot ($(L,R)$)

One of the two distinguished positions, left or right, at a vertex of a binary tree. Each binary tree child slot is occupied by a child and its subtree, or is empty. A reference representation can use null for an empty binary tree child slot. Two slots are capacity for at most two children in a rooted tree, rather than a requirement for two actual vertices.

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. ThereforeThis 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.