Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
2  
@Rick: Now that you mention it, yes. –  Brian M. Scott Dec 12 '12 at 0:43
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
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
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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