0
$\begingroup$

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

  • 0
    yeah I know that they could be put in bijection with an intermediary. I'd like a direct bijection2011-09-20

1 Answers 1

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

  • 0
    @Alex: In his graph theory book West does say at one point that in many contexts it’s naturally assumed that binary trees are full, so it’s possible that he’s made that assumption in this problem and inadvertently failed to say so.2011-09-21