TAOCP 2.3 Exercise 20
Let $I(T)$ denote the number of internal nodes, namely nodes having two children, and let $L(T)$ denote the number of leaves.
Exercise 20. ▶ [**] [M21] Define a 0-2-tree as a tree in which each node has exactly zero or two children. (Formally, a 0-2-tree consists of a single node, called its root, plus 0 or 2 disjoint 0-2-trees.) Show that every 0-2-tree has an odd number of nodes; and give a one-to-one correspondence between binary trees with $n$ nodes and (ordered) 0-2-trees with $2n + 1$ nodes.
Verified: no
Solve time: 28s
Let $I(T)$ denote the number of internal nodes, namely nodes having two children, and let $L(T)$ denote the number of leaves. For a 0-2-tree, every node is either internal or a leaf, so the total number of nodes is $I(T)+L(T)$. Every internal node contributes exactly two edges to its children; hence the number of edges is $2I(T)$. Since every tree with $I(T)+L(T)$ nodes has $(I(T)+L(T))-1$ edges, we obtain
$$ 2I(T)=I(T)+L(T)-1, $$
therefore
$$ L(T)=I(T)+1. $$
The total number of nodes is then
$$ I(T)+L(T)=2I(T)+1, $$
which is odd.
A one-to-one correspondence with binary trees is obtained as follows. Given a binary tree, attach to every node two ordered children positions. If a node lacks a left child, insert a leaf in the left position; if it lacks a right child, insert a leaf in the right position. Original children remain unchanged. Every original node then has exactly two children, so the result is an ordered 0-2-tree. If the binary tree has $n$ nodes, it has $n-1$ actual child links. Thus among the $2n$ child positions, exactly $2n-(n-1)=n+1$ are empty and become new leaves. The resulting 0-2-tree therefore has
$$ n+(n+1)=2n+1 $$
nodes. Conversely, given an ordered 0-2-tree with $2n+1$ nodes, delete all leaves. The remaining nodes form a binary tree with $n$ nodes, since a 0-2-tree with $2n+1$ nodes has $n+1$ leaves and $n$ internal nodes. These two constructions are inverse to one another, establishing a one-to-one correspondence between binary trees with $n$ nodes and ordered 0-2-trees with $2n+1$ nodes.
$$ \boxed{\text{Binary trees with }n\text{ nodes } \longleftrightarrow \text{ ordered 0-2-trees with }2n+1\text{ nodes}.} $$