3
$\begingroup$

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!

  • 2
    @Rick: Now that you mention it, [yes](http://math.stackexchange.com/questions/250851/bijection-between-binary-trees-and-plane-trees).2012-12-12

1 Answers 1

2

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.

  • 1
    @Nizbel99: I’ve no idea why it says that: the mapping that I described is clearly reversible.2012-12-12