User:Antti Karttunen/Recursive transformations of binary tree bijections

Recursive transformations of binary tree bijections are transformations which transform a bijection of rooted plane binary trees recursively to another bijection of binary trees. Formally, if the set $\scriptstyle B\,$ consists of all possible bijections $\scriptstyle b\;:\;S\;\rightarrow \;S\,$, where $\scriptstyle S\,$ is the set of all rooted plane binary trees, then a transformation $\scriptstyle T\,$ of binary tree bijections is a function $\scriptstyle T\;:\;B\;\rightarrow \;B\,$ whose domain is the whole set $\scriptstyle B\,$.

Note that recursive doesn't refer here to recursive sets or recursive enumerability but concretely to structural recursion inherent in the structure of binary trees. Many of these transformations are based on preorder, inorder and postorder variants of the depth-first search of binary trees or general trees.

List of common recursive transformations

Below are listed some of the most essential transformations applicable to bijections of binary trees. In the explanations given, $\scriptstyle f\,$ stands for the bijection given, and $\scriptstyle g\,$ for the (usually different) bijection that is obtained from $\scriptstyle f\,$ with some transformation $\scriptstyle T\,$ as $\scriptstyle g\;=\;T(f)\,$.

The notation $f_{L}$ refers to a Catalan bijection that applies $\scriptstyle f\,$ only to the left-hand side child of a binary tree, and leaves the right-hand side intact, and similarly, the notation $f_{R}$ refers to a Catalan bijection that applies $f$ only to the right-hand side child of a binary tree, and leaves the left-hand side intact. In Scheme these could be expressed as:

(define (fL s) (cons (f (car s)) (cdr s)))

and

(define (fR s) (cons (car s) (f (cdr s))))

This notation comes handy for showing what are the inverse operations for each transformation.

Many of these recursive transformations can also be implemented as folds. The relationships between the recursive transformation operators, formulas for their inverses, etc. are given below without proofs. For proofs and various implications of folds, please consult.

FORK

In this recursion scheme the bijection $\scriptstyle f\,$ is first applied at the root of binary tree, before the algorithm recurses down to the both branches (new ones, possibly changed by $\scriptstyle f\$). This corresponds to the pre-order (prefix) traversal of the binary tree. The name stems from the fact that the recursion "forks" into both branches of a binary tree.

If $\scriptstyle g\;=\;FORK(f)\,$ then the inverse of the resulting Catalan bijection $\scriptstyle g\,$ is obtained as $\scriptstyle g^{-1}\;=\;KROF(f^{-1})\,$. See below for the definition of KROF.

FORK is a bijective function on the set $\scriptstyle B\,$, which means that any Catalan bijection can be obtained with FORK-transform from another Catalan bijection. Its inverse operator $\scriptstyle FORK^{-1}\,$ (i.e. $\scriptstyle g\;=\;FORK(f)\;\iff \;f\;=\;FORK^{-1}(g)\,$) is formed as a function composition $\scriptstyle FORK^{-1}(g)\;=\;g_{L}^{-1}\;\circ \;g_{R}^{-1}\;\circ \;g\,$.

The Scheme-functions FORK and !FORK given below can be used to obtain such a transformed bijection from any constructively or destructively implemented bijection.

(define (FORK foo)
  (letrec ((bar (lambda (s)
                  (let ((t (foo s)))
                    (if (pair? t)
                        (cons (bar (car t)) (bar (cdr t)))
                        t
                    )
                  )
                )
          ))
     bar
  )
)

(define (!FORK foo!)
  (letrec ((bar! (lambda (s)
                    (cond ((pair? s)
                            (foo! s)
                            (bar! (car s))
                            (bar! (cdr s))
                          )
                    )
                    s
                 )
          ))
     bar!
  )
)

KROF

In this recursion scheme the algorithm first recurses down to the both branches, and the bijection $\scriptstyle f\,$ is applied at the root of binary tree only after the execution has returned from the recursion. In other words, this corresponds to the post-order (postfix) traversal of a binary tree. The Scheme-functions KROF and !KROF given below can be used to obtain such a transformed bijection from any constructively or destructively implemented bijection. Note how KROF has been implemented as a fold.

If $\scriptstyle g\;=\;KROF(f)\,$ then the inverse of the resulting Catalan bijection $\scriptstyle g\,$ is obtained as $\scriptstyle g^{-1}\;=\;FORK(f^{-1})\,$. See above for the definition of FORK.

KROF is a bijective function on the set $\scriptstyle B\,$, which means that any Catalan bijection can be obtained with KROF-transform from another Catalan bijection. Its inverse operator $\scriptstyle KROF^{-1}\,$ (i.e. $\scriptstyle g\;=\;KROF(f)\;\iff \;f\;=\;KROF^{-1}(g)\,$) is formed as a function composition $\scriptstyle KROF^{-1}(g)\;=\;g\;\circ \;g_{L}^{-1}\;\circ \;g_{R}^{-1}\,$.

(define (KROF foo) (letrec ((bar (lambda (s) (fold-right (lambda (x y) (foo (cons (bar x) y))) '() s)))) bar))

(define (!KROF foo!)
  (letrec ((bar! (lambda (s)
                    (cond ((pair? s)
                            (bar! (car s))
                            (bar! (cdr s))
                            (foo! s)
                          )
                    )
                    s
                 )
          ))
     bar!
  )
)

SPINE

In this recursion scheme the algorithm the bijection $\scriptstyle f\,$ is first applied at the root of binary tree, before the algorithm recurses down to the new (possibly changed by $\scriptstyle f\,$) right-hand side branch. The name comes from the fact in this scheme only the "spine" of the binary tree (leaning to the right) is traversed, but the recursion does not dive into the left-hand side branches.

If $\scriptstyle g\;=\;SPINE(f)\,$ then the inverse of the resulting Catalan bijection $\scriptstyle g\,$ is obtained as $\scriptstyle g^{-1}\;=\;ENIPS(f^{-1})\,$. See below for the definition of ENIPS.

SPINE is a bijective function on the set $\scriptstyle B\,$, which means that any Catalan bijection can be obtained with SPINE-transform from another Catalan bijection. Its inverse operator $\scriptstyle SPINE^{-1}\,$ (i.e. $\scriptstyle g\;=\;SPINE(f)\;\iff \;f\;=\;SPINE^{-1}(g)\,$) is formed as a function composition $\scriptstyle SPINE^{-1}(g)\;=\;g_{R}^{-1}\;\circ \;g\,$.

The Scheme-functions SPINE and !SPINE given below can be used to obtain such a transformed bijection from any constructively or destructively implemented bijection.

(define (SPINE foo)
  (letrec ((bar (lambda (s)
                  (let ((t (foo s)))
                    (if (pair? t)
                        (cons (car t) (bar (cdr t)))
                        t
                    )
                  )
                )
          ))
     bar
  )
)

(define (!SPINE foo!)
  (letrec ((bar! (lambda (s)
                    (cond ((pair? s)
                            (foo! s)
                            (bar! (cdr s))
                          )
                    )
                    s
                 )
          ))
     bar!
  )
)

ENIPS

In this recursion scheme the algorithm first recurses down to the right-hand side branch of the binary tree, and only after it has returned from the recursion, the bijection $\scriptstyle f\,$ is applied at the root of the tree.

If $\scriptstyle g\;=\;ENIPS(f)\,$ then the inverse of the resulting Catalan bijection $\scriptstyle g\,$ is obtained as $\scriptstyle g^{-1}\;=\;SPINE(f^{-1})\,$. See above for the definition of SPINE.

ENIPS is a bijective function on the set $\scriptstyle B\,$, which means that any Catalan bijection can be obtained with ENIPS-transform from another Catalan bijection. Its inverse operator $\scriptstyle ENIPS^{-1}\,$ (i.e. $\scriptstyle g\;=\;ENIPS(f)\;\iff \;f\;=\;ENIPS^{-1}(g)\,$) is formed as a function composition $\scriptstyle ENIPS^{-1}(g)\;=\;g\;\circ \;g_{R}^{-1}\,$.

The Scheme-functions ENIPS and !ENIPS given below can be used to obtain such a transformed bijection from any constructively or destructively implemented bijection. Note how ENIPS has been implemented as a fold.

(define (ENIPS foo) (lambda (s) (fold-right (lambda (x y) (foo (cons x y))) '() s)))

(define (!ENIPS foo!)
  (letrec ((bar! (lambda (s)
                    (cond ((pair? s)
                            (bar! (cdr s))
                            (foo! s)
                          )
                    )
                    s
                 )
          ))
     bar!
  )
)

DEEPEN

In this recursion scheme the bijection $\scriptstyle f\,$ is first applied at the root of general tree, before the algorithm recurses down to all subtrees (new ones, possibly changed by $\scriptstyle f\,$). This corresponds to the pre-order (prefix) traversal of a Catalan structure, when it is interpreted as a general tree in the standard way. The name stems from the fact that this transformation transforms a "shallow" variant of certain Catalan bijections (when viewed as automorphisms of plane general trees) to the corresponding "deep" variants. Examples include:

$*A057164=DEEPEN(*A057508)$ Transform a shallow (ordinary) reverse of lists to "deep-reverse".

$*A057511=DEEPEN(*A057509)$

$*A057512=DEEPEN(*A057510)$

If $\scriptstyle g\;=\;DEEPEN(f)\,$ then the inverse of the resulting Catalan bijection $\scriptstyle g\,$ is obtained as $\scriptstyle g^{-1}\;=\;NEPEED(f^{-1})\,$. See below for the definition of NEPEED.

DEEPEN is a bijective function on the set $\scriptstyle B\,$, which means that any Catalan bijection can be obtained with DEEPEN-transform from another Catalan bijection. Its inverse operator $\scriptstyle DEEPEN^{-1}\,$ (i.e. $\scriptstyle g\;=\;DEEPEN(f)\;\iff \;f\;=\;DEEPEN^{-1}(g)\,$) is formed as a function composition $\scriptstyle DEEPEN^{-1}(g)\;=\;RIBS(g^{-1})\;\circ \;g\,$. See below for the definition of RIBS.

FORK is the composition of DEEPEN and SPINE, i.e. the following holds for all bijections $\scriptstyle f\,$: $\scriptstyle FORK(f)=DEEPEN(SPINE(f))\,$.

The Scheme-functions DEEPEN and !DEEPEN given below can be used to obtain such a transformed bijection from any constructively or destructively implemented bijection.

(define (DEEPEN foo) (letrec ((bar (lambda (s) (map bar (foo s))))) bar))
;; Alternatively, implemented as a fold:
(define (DEEPEN g) (letrec ((h (lambda (s) (fold-right (lambda (x y) (cons (h x) y)) ’() (g s))))) h))

(define (!DEEPEN foo!) (letrec ((bar! (lambda (s) (foo! s) (for-each bar! s) s))) bar!))

NEPEED

In this recursion scheme the bijection $\scriptstyle f\,$ the algorithm first recurses down to all subtrees, and only after it has returned from the recursion, the bijection $\scriptstyle f\,$ is applied at the root of the general tree. I.e. this corresponds to the post-order (postfix) traversal of a Catalan structure, when it is interpreted as a general tree.

If $\scriptstyle g\;=\;NEPEED(f)\,$ then the inverse of the resulting Catalan bijection $\scriptstyle g\,$ is obtained as $\scriptstyle g^{-1}\;=\;DEEPEN(f^{-1})\,$. See above for the definition of DEEPEN.

NEPEED is a bijective function on the set $\scriptstyle B\,$, which means that any Catalan bijection can be obtained with NEPEED-transform from another Catalan bijection. Its inverse operator $\scriptstyle NEPEED^{-1}\,$ (i.e. $\scriptstyle g\;=\;NEPEED(f)\;\iff \;f\;=\;NEPEED^{-1}(g)\,$) is formed as a function composition $\scriptstyle NEPEED^{-1}(g)\;=\;g\;\circ \;RIBS(g^{-1})\,$.

KROF is the composition of NEPEED and ENIPS, i.e. the following holds for all bijections $\scriptstyle f\,$: $\scriptstyle KROF(f)=NEPEED(ENIPS(f))\,$.

The Scheme-functions NEPEED and !NEPEED given below can be used to obtain such a transformed bijection from any constructively or destructively implemented bijection.

(define (NEPEED foo) (letrec ((bar (lambda (s) (foo (map bar s))))) bar))
;; Alternatively, implemented as a fold:
(define (NEPEED g) (letrec ((h (lambda (s) (g (fold-right (lambda (x y) (cons (h x) y)) ’() s))))) h))

(define (!NEPEED foo!) (letrec ((bar! (lambda (s) (for-each bar! s) (foo! s) s))) bar!))

INORDER

In this recursion scheme the bijection $\scriptstyle f\,$ is applied at the root of binary tree after the algorithm has recursed down the car-branch (the left hand side tree in the context of binary trees), but before the algorithm recurses down to the cdr-branch (the right hand side of the binary tree, with respect to the new orientation of branches, possibly changed by the bijection $\scriptstyle f\,$). I.e. this corresponds to the depth-first in-order traversal of a rooted plane binary tree.

If $\scriptstyle g\;=\;INORDER(f)\,$ then the inverse of the resulting Catalan bijection $\scriptstyle g\,$ is obtained as $\scriptstyle g^{-1}\;=\;REDRONI(f^{-1})\,$. See below for the definition of REDRONI.

INORDER is a bijective function on the set $\scriptstyle B\,$, which means that any Catalan bijection can be obtained with INORDER-transform from another Catalan bijection. Its inverse operator $\scriptstyle INORDER^{-1}\,$ (i.e. $\scriptstyle g\;=\;INORDER(f)\;\iff \;f\;=\;INORDER^{-1}(g)\,$) is formed as a function composition $\scriptstyle INORDER^{-1}(g)\;=\;g_{R}^{-1}\;\circ \;g\;\circ \;g_{L}^{-1}\,$.

The Scheme-functions INORDER and !INORDER below can be used to obtain such a transformed bijection from any constructively (or respectively: destructively) implemented bijection.

(define (INORDER f)
  (letrec ((g (lambda (s)
                (cond ((not (pair? s)) s)
                      (else (let ((t (f (cons (g (car s)) (cdr s)))))
                              (cons (car t) (g (cdr t)))
                            )
                      )
                )
              )
          ))
     g
  )
)

(define (!INORDER f!)
  (letrec ((g! (lambda (s)
                    (cond ((pair? s)
                            (g! (car s))
                            (f! s)
                            (g! (cdr s))
                          )
                    )
                    s
                 )
          ))
     g!
  )
)

REDRONI

In this recursion scheme the bijection $\scriptstyle f\,$ is applied at the root of binary tree after the algorithm has recursed down the cdr-branch (the right hand side tree in the context of binary trees) and returned from that recursion, but before the algorithm recurses down to the car-branch (the left hand side of the binary tree, with respect to the new orientation of branches, possibly changed by the bijection $\scriptstyle f\,$). I.e. this corresponds to the reversed depth-first in-order traversal of a binary tree.

If $\scriptstyle g\;=\;REDRONI(f)\,$ then the inverse of the resulting Catalan bijection $\scriptstyle g\,$ is obtained as $\scriptstyle g^{-1}\;=\;INORDER(f^{-1})\,$. See above for the definition of INORDER.

REDRONI is a bijective function on the set $\scriptstyle B\,$, which means that any Catalan bijection can be obtained with REDRONI-transform from another Catalan bijection. Its inverse operator $\scriptstyle REDRONI^{-1}\,$ (i.e. $\scriptstyle g\;=\;REDRONI(f)\;\iff \;f\;=\;REDRONI^{-1}(g)\,$) is formed as a function composition $\scriptstyle REDRONI^{-1}(g)\;=\;g_{L}^{-1}\;\circ \;g\;\circ \;g_{R}^{-1}\,$.

The Scheme-functions REDRONI and !REDRONI below can be used to obtain such a transformed bijection from any constructively (or respectively: destructively) implemented bijection.

(define (REDRONI f)
   (letrec ((g (lambda (s)
                  (fold-right (lambda (x y) (let ((t (f (cons x y)))) (cons (g (car t)) (cdr t))))
                              '()
                              s
                  )
               )
           ))
           g
   )
)


(define (!REDRONI f!)
  (letrec ((g! (lambda (s)
                    (cond ((pair? s)
                            (g! (cdr s))
                            (f! s)
                            (g! (car s))
                          )
                    )
                    s
                 )
          ))
     g!
  )
)

RIBS

In this recursion scheme the bijection $f$ is applied to all (toplevel) subtrees of the Catalan structure, when it is interpreted as a general tree. In the S-expression/list-context of programming languages Lisp and Scheme, it corresponds to applying (mapcar f s) (or respectively, $map$ instead of $mapcar$ in Scheme) to the S-expression $s$. The name adopted here stems from the fact that the bijection $f$ affects only the "ribs" branching leftward from the "spine" of the binary tree.

If $g=RIBS(f)$ then $g^{-1}=RIBS(f^{-1})$. Note that in contrast to all previous transformations, RIBS has no inverse. That is, most of the times, when $g$ is an arbitrary Catalan bijection, it cannot be obtained as $g=RIBS(f)$ from some other bijection $f$.

The Scheme-functions RIBS and !RIBS given below can be used to obtain such a transformed bijection from any constructively or destructively implemented bijection.

(define (RIBS foo) (lambda (s) (map foo s)))
;; Or alternatively, as a fold:
(define (RIBS f) (lambda (s) (fold-right (lambda (x y) (cons (f x) y)) ’() s)))

(define (!RIBS foo!) (lambda (s) (for-each foo! s) s))

Note that $RIBS(f)$ is really just a short-hand for $SPINE(f_{L})$ = $ENIPS(f_{L})$.

If an integer sequence $F_{f}$ counts the number of fixed points (among each A000108($n$) structures of size $n$) of the Catalan bijection $f$, then the number of fixed points of the bijection $g=RIBS(f)$ are counted respectively by $F_{g}=INVERT(RIGHT(F_{f}))$, where operator $RIGHT$ increases the indices of the sequence $F_{f}$ by one (from zero to one-based sequence), and transform INVERT is the one which Cameron calls the operator $\scriptstyle A\,$ in and for which Bernstein and Sloane gave the name INVERT in.

Authorship

The first version of this page was written by Antti Karttunen Aug 22, 2012, based on sections 8 (Recursion Schemata) and 9 (Implementing Recursion Schemata as Folds, Implications of Folds) of his unfinished draft, version 26 July 2011.

Cite this page as

A. Karttunen, <insert your name here if you added anything essential>, et al., <a href="http://oeis.org/wiki/Recursive_transformations_of_binary_tree_bijections">Recursive transformations of binary tree bijections</a>, OEIS Wiki.