The following bijection on rooted plane trees arises in the following context : the counting sequence of (rooted plane) trees with $n$ edges ($n+1$ vertices) and $k$ leaves is given by:

$$\frac{1}{n} {n \choose k} {n \choose k-1}$$

a sequence of numbers called the Narayana numbers, and they help to answer a question asked on math.SE to understand their symmetry in the number of leaves (replacing $k$ by $n-k-1$ in the above formula does not change its value).

The map is defined as follows (take your pencil !) : to a (rooted plane) tree on $n$ vertices, we will associate another (rooted plane) tree with $n$ vertices, by keeping the same vertex set (also the same root) and changing the edge set. To that end, it is enough to define the father of every vertex distinct from the root in the new tree, let's call it the **new father.**

Define a brother of a (non-root) vertex as a child of the same father. Consider a non-root vertex and look for the **most recent ancestor** of that vertex that has a **brother to its right** : this will the vertex itself if it has a brother to its right, or the father of this vertex if the vertex itself has no brother to its right but its father has, and so on...

In case there is such an ancestor : the new father is the

**brother immediately to the right**of that ancestor.In case there is no such ancestor : the new father is the root of the tree.

The root is left unchanged.

The reciprocal map is obtained by replacing the word "right" by the word "left" in the above description.

The map sends a tree on $n$ edges and $k$ leaves to a tree with the same number of edges but $n-k-1$ leaves.

(This is closely related, but distinct from what is called rotation bijection in computer science, see Flajolet and Sedgewick on p.73.)

Question : Has anyone already seen this map (or a close relative of it) in the literature ? For what use ?