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

  • $\begingroup$ (After googling:) One way is to put them both in bijection with an intermediary: Dyck words. See slide 9 of this presentation. $\endgroup$ – anon Sep 20 '11 at 23:39
  • $\begingroup$ yeah I know that they could be put in bijection with an intermediary. I'd like a direct bijection $\endgroup$ – Mec Sep 20 '11 at 23:48

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

  • $\begingroup$ this is an exercise from the book of douglas west and it doesn't require the binary tree to be full. Are you sure of that? $\endgroup$ – Mec Sep 21 '11 at 3:56
  • $\begingroup$ @Alex: Reasonably sure, yes. If that’s Douglas B. West’s Introduction to Graph Theory, I have the second edition; which problem is it? $\endgroup$ – Brian M. Scott Sep 21 '11 at 4:11
  • $\begingroup$ It's the book "combinatorial mathematics" pag 59 exercise 1.3.27 $\endgroup$ – Mec Sep 21 '11 at 4:20
  • $\begingroup$ @Alex: That I don’t have. (Has it even been published yet? What I see on the web suggests that he’s still revising it.) It can’t binary trees in general, because for each $n$ there are infinitely many binary trees with $n+1$ leaves: just find one, and keep extending one of its branches. You can find a bijection between ordered trees with $n+1$ vertices and arbitrary binary trees with $n$ vertices ($T\leftrightarrow T_B$) and between these and full binary trees with $n+1$ leaves, but pinning down the number of leaves of an arbitrary binary tree isn’t enough. $\endgroup$ – Brian M. Scott Sep 21 '11 at 4:42
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Sep 21 '11 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.