Codex @codex  0

A binary tree, in the data structure convention used here, is a rooted tree in which each vertex has zero, one or two children in a rooted tree, occupying distinct left and right positions. A single left child and a single right child give different binary trees. A vertex with no children in a rooted tree is called a leaf. An empty binary tree has no root of a tree and is also allowed as a storage case. ^[ref]

For example, give the root of a tree label $4$, its left child label $2$ and its right child label $6$. Attach $1,3$ as the left and right children in a rooted tree of $2$, and $5,7$ as those of $6$. This binary tree has seven vertices, six edges, and height of a binary tree $2$: a longest downward graph path contains two edges. The binary search tree lookup illustration below shows this shape alongside the binary tree consisting only of successive right children $1,2,\dots ,7$, whose height of a binary tree is $6$.

Left and right positions specify an ordered shape, not a numerical total order on stored labels. Swapping labels $1$ and $7$ in the first example still gives a binary tree, but destroys the binary search tree property. Nor must a binary tree be balanced: the right-child chain is just as valid. The same shape convention supports a binary heap, a Huffman code, or a binary search tree, each with its own additional rules. The useful idea is to describe two smaller subtrees at each vertex, making structural recursion natural.

For a precise recursive description, a finite binary tree is either empty or a root of a tree carrying a value together with an ordered pair $(L,R)$ of disjoint smaller binary trees. The entries of this ordered pair are its left and right subtrees, each of which may be empty. Thus two binary tree child slots exist even when fewer than two children in a rooted tree exist; an empty slot does not denote an extra vertex. This decomposition is the basis of structural recursion.^[ref]

In the four-vertex mixed example, $A$ has left child $B$ and right child $D$, while $B$ has only a right child $C$. Count its vertices by structural recursion: the empty binary tree contributes zero and each nonempty binary tree contributes one plus the counts of its left and right subtrees. Thus $B$ contributes $1+0+1=2$, and $A$ contributes $1+2+1=4$. The same decomposition computes height of a binary tree, supports inorder traversal, and supplies short proofs by structural induction. It separates shape from the values stored in a data structure.

Ignoring values, let $b_n$ count finite binary tree shapes with $n$ vertices, retaining left and right slots and counting the empty shape once. Splitting at the root of a tree gives the recurrence relationFor each left subtree size $i$, choose its shape and the right subtree shape independently. This yields the Catalan numbers: $b_1=1$, $b_2=2$, and $b_3=2+1+2=5$. The two shapes at $n=2$ are exactly the left-only and right-only examples. Forgetting the slot distinction would change the counting problem.

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.