# Bijection Between Binary Rooted Trees and Planar Planted Trees

I was wondering if anyone could describe (or point me too) a description of a bijection between binary rooted trees and planar planted trees. My professor told me that this might be useful to know for our final exam in enumeration. How would I go about to transform a BRT into a PPT (and vice-versa)? I am familiar with the bijection between BRTs to Well Formed Parenthesization, and Well Formed Parenthesization to PPTs, but not a bijection between BRTs and PPTs directly.

Thanks!

-
Didn't we see a very similar question in the past week? I couldn't find one, so perhaps my memory is failing. As usual. – Rick Decker Dec 12 '12 at 0:42
@Rick: Now that you mention it, yes. – Brian M. Scott Dec 12 '12 at 0:43

Let $T$ be a planar rooted tree and $T'$ the corresponding binary rooted tree; $T$ and $T'$ have the same root and vertices and differ only in the edges. For any vertex $v$, the left child of $v$ in $T'$ is the eldest child of $v$ in $T$ (if $v$ has children in $T$), and the right child of $v$ in $T'$ is the eldest younger sibling of $v$ in $T$ (if $v$ has younger siblings in $T$).

Added: Wikipedia has a description that includes a concrete example.

-
Is there another procedure for going the other way? The Wikipedia entry states that the one you describe may only work one-way? Why is that? – Nizbel99 Dec 12 '12 at 1:32
@Nizbel99: I’ve no idea why it says that: the mapping that I described is clearly reversible. – Brian M. Scott Dec 12 '12 at 1:37