Explicit bijection between ordered trees with $n+1$ vertices and binary trees with $n+1$ leaves

Question

What is an example of a direct bijection between ordered trees with $n+1$ vertices and binary trees with $n+1$ leaves?

Answer 1

Let $T$ be an ordered tree with $n+1$ vertices $v_0,v_1,\dots,v_n$, where $v_0$ is the root. For convenience in talking about them, I’ll think of the children of a vertex as being ordered from eldest to youngest (pictorially from left to right). We’ll begin by building a binary tree $B_T$ on the same vertices, also with root $v_0$:

• For each vertex $v_k$, the left child of $v_k$ in $B_T$ is the first child of $v_k$ in $T$; if $v_k$ is a leaf of $T$, it has no left child in $B_T$.
• For each vertex $v_k$, the right child of $v_k$ is the next younger sibling of $v_k$ in $T$, if there is one; otherwise $v_k$ has no right child in $B_T$.

The root $v_0$ will have a left child and no right child. Without loss of generality we may assume that $v_1$ is the left child of $v_0$. Remove $v_0$ and the edge from $v_0$ to $v_1$; what’s left is a binary tree $B_T'$ with $n$ vertices and root $v_1$. Now expand $B_T'$ to a full binary tree in the following way.

Consider each vertex of $B_T'$ in turn. If a vertex has both a left and a right child, do nothing to it. If it has only a left child, add a new right child. If it has only a right child, add a new left child. And if it’s a leaf and so has neither a left nor a right child, add one of each. Call the resulting full binary tree $F_T$. Each of the $n$ vertices of $B_T'$ is an internal vertex of $F_T$ and therefore has two children, so $F_T$ has $2n$ edges. Since it’s a tree, $F_T$ must therefore have $2n+1$ vertices, and since $n$ of these vertices are internal, $F_T$ must have $n+1$ leaves.

The reverse conversion is fairly straightforward. Start with a full binary tree $F$ with $n+1$ leaves. Stripping off the leaves and their associated edges leaves a binary tree with $n$ vertices. Make the root of this tree the left child of a new root to get a binary tree with $n+1$ vertices. Finally, reverse the contstruction that led from $T$ to $B_T$ to get an ordered tree with $n+1$ vertices. You’ll have to convince yourself that this can be done, and that these processes really are inverses of each other, but this gives you an explicit bijection. (Technically there’s an intermediary $-$ binary trees on $n$ vertices $-$ but they come naturally out of the construction and are the same kind of animal, unlike Dyck words.)