Binary trees, defined recursively, and their size

Let $\{0,1{\}}^{\ast }:={\bigcup }_{\mathrm{\ell }\in \mathbb{N}}\{0,1{\}}^{\mathrm{\ell }}$ be the set of all finite words over $\{0,1\}$ (Finite words, contiguous factors, avoidance and proper-prefix states, The natural numbers $\mathbb{N}$ (von Neumann)), written $\epsilon$ for the empty word and $wb$ for the word $w$ followed by the letter $b$. A word $u$ is a prefix of $w$ when $w=uz$ for some $z$.

Definition. A binary tree is a finite set $T\subseteq \{0,1{\}}^{\ast }$ (The cardinality $\mid A\mid$ of a finite set) such that

1. $\epsilon \in T$;
2. $T$ is closed under prefixes: if $wb\in T$ with $b\in \{0,1\}$ then $w\in T$;
3. for every $w\in T$: $w0\in T$ if and only if $w1\in T$.

Its elements are nodes; a node $w$ is internal when $w0\in T$, and a leaf otherwise. The size of $T$ is the number of internal nodes, $\mathrm{size}(T):=\mid \{w\in T:w0\in T\}\mid ,$ a natural number because $T$ is finite (A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$). Write $\mathcal{T}$ for the set of binary trees, a subset of $\mathcal{P}(\{0,1{\}}^{\ast })$ (The power set $\mathcal{P}(x)=\{z:z\subseteq x\}$), and ${\mathcal{T}}_n:=\{T\in \mathcal{T}:\mathrm{size}(T)=n\}$.

The trees of size $0$. If $\mathrm{size}(T)=0$ then no node of $T$ is internal, so no node has a child; a nonempty word $wb$ in $T$ would put $w$ in $T$ by clause 2 with $wb$ a child of it, so $T=\{\epsilon \}$. Conversely $\{\epsilon \}$ is a binary tree of size $0$. Hence ${\mathcal{T}}_0=\{\{\epsilon \}\}$, a one-element set: the tree with no internal node at all.

The recursion, proved here because everything below uses it. Let $T\in \mathcal{T}$ with $T\mathrm{\ne }\{\epsilon \}$; then $\epsilon$ is internal, so $0\in T$ and, by clause 3, $1\in T$. Put

$L:=\{w:0w\in T\},R:=\{w:1w\in T\}\mathrm{.}$

Both are binary trees: each contains $\epsilon$, each is prefix-closed because $T$ is, each satisfies clause 3 because $T$ does, and each is finite because $w\mapsto 0w$ and $w\mapsto 1w$ inject them into $T$. The internal nodes of $T$ are $\epsilon$ together with the words $0w$ for $w$ internal in $L$ and $1w$ for $w$ internal in $R$, and these three families are pairwise disjoint, so The sum rule: a finite disjoint union is finite with $\mid A\cup B\mid =\mid A\mid +\mid B\mid$ and $\mid {\bigcup }_{i\in I}{A}_i\mid ={\sum }_{i\in I}\mid A_i\mid$, and a sum over a finite index set splits along a partition gives

$\mathrm{size}(T)=1+\mathrm{size}(L)+\mathrm{size}(R)\mathrm{.}$

Conversely, for binary trees $L$ and $R$ the set $T:=\{\epsilon \}\cup \{0w:w\in L\}\cup \{1w:w\in R\}$ is a binary tree with those two sets recovered as above, and with size $1+\mathrm{size}(L)+\mathrm{size}(R)$. The two constructions undo one another, so for every $n\in \mathbb{N}$ the map $T\mapsto (\mathrm{size}(L),L,R)$ is a bijection

${\mathcal{T}}_{n+1}⟶\{(i,L,R):i\le n,L\in {\mathcal{T}}_i,R\in {\mathcal{T}}_{n-i}\}\mathrm{.}$

Small cases. ${\mathcal{T}}_1$ has the single member $\{\epsilon ,0,1\}$, and ${\mathcal{T}}_2$ has exactly two members, obtained by attaching the size-one tree on the left or on the right.

• No graph theory is used, and none is available at this point in the reading order. A binary tree here is a set of node addresses: a finite prefix-closed set of binary words in which a node has two children or none. The usual picture, with a root drawn at the top and two subtrees hanging from it, is an illustration of the recursion clause above and is not a hypothesis anywhere.

• Size counts internal nodes, not nodes. A tree of size $n$ has $n$ internal nodes and, by the recursion clause and induction, $n+1$ leaves; the count that matches the Catalan numbers is the one above. A statement about trees with $n$ nodes would be a different statement.

• Why the addresses and not ordered pairs. Defining a tree as $\bullet$ or an ordered pair of trees would need a recursion whose values are sets and whose ambient collection is not a set at this point in the development. The address encoding puts every tree inside the fixed set $\mathcal{P}(\{0,1{\}}^{\ast })$, so the definition is a condition rather than a construction, and the recursion clause above is then a theorem about it.