| Object type | |
| Number $n$ of vertices | (max. 10) |
| Arity $k$ | |
| Output format | |
An algorithm for generating all binary trees by tree rotations was proposed by Lucas, Roelants van Baronaigien, and Ruskey [LRvBR93]. Williams [Wil13] discovered an amazingly simple description of this method in terms of a greedy algorithm: Start with the all-right tree, and then repeatedly perform a tree rotation involving the largest possible vertex that creates a previously unvisited tree. A generalization of this method from binary trees $k=2$ to larger values of $k$ was proposed in the paper [AMV24], and this is the algorithm running on this website. The existence of a tree rotation Gray code for $k\geq 3$ was already proved earlier by Huemer, Hurtado and Pfeifle [HHP08]. Interestingly, under the bijection discussed above, tree rotations translate to flips in dissections, where each flip operation removes an edge between two $(k+1)$-gons, creating a $2k$-gon, and replaces it by another diagonal in that $2k$-gon.
The graphical output for our algorithm shows the dissection corresponding to each tree (any two consecutive dissections differing in a flip), and the textual output is obtained as follows: The vertices of the tree are labeled with $1,\ldots,n$ according to the search tree property, i.e., for any vertex $i$, all vertices in the leftmost subtree are smaller than $i$, and all vertices in the remaining $k-1$ subtrees are larger than $i$, and they appear increasingly from left to right in the subtrees. The tree is then traversed in a preorder traversal, i.e., we first record the root of the tree, followed by recursively recording vertices in the subtrees of the root, where subtrees are processed from left to right. An empty subtree is printed as 0. For example, the ternary tree from the figure would be labeled as above and printed as 2 1 0 0 0 7 4 3 0 0 0 5 0 0 0 6 0 0 0 0 0 9 8 0 0 0 10 0 0 0 0.
A variation on this theme was proposed by Sagan [Sag08]. He considers triangulations of a convex $N$-gon in which the points are colored red and blue alternatingly, with the additional requirement that every triangle has vertices of both colors. As monochromatic triangles are forbidden, such a triangulation is called colorful. It was proved in [AMV24] that for $N\geq 8$ all colorful triangulations can be listed in Gray code order, i.e., any two consecutive colorful triangulations differ in a flip, and the algorithm described in that paper runs on the website. In the textual output of the algorithm, each colorful triangulation is encoded as pair of a tree and a bitstring, separated by |. For even $N$, the tree is a ternary tree, and it is the dual graph of the quadrangulation obtained by removing all monochromatic inner edges from the triangulation (leaving only the colorful inner edges), and the bitstring describes a vertex-coloring of the tree, where colors 0 and 1 represent a (red,red) or (blue,blue) edge, respectively, inside the quadrangle corresponding to the vertex of the tree. For example, the colorful triangulation shown below would be printed as 2 1 0 0 0 7 4 3 0 0 0 5 0 0 0 6 0 0 0 0 0 9 8 0 0 0 10 0 0 0 0 | 0000011001, where the first part represents the ternary tree corresponding to the quadrangulation above, and the bitstring encodes that vertices 6,7 and 10 are blue, and all others red (three (blue,blue)-edges in the corresponding quadrangles, and seven (red,red)-edges in the other quadrangles).
For odd $N$, the tree is restricted in that the largest vertex has to appear on the right branch starting from the root and its color never changes (it is always blue, corresponding to two consecutive blue points of the $N$-gon). For generating all colorful triangulations, the algorithm essentially combines the ternary tree rotation Gray code discussed before with the binary reflected Gray code for generating all bitstrings. This has to be done with some care to ensure that flips of colorful edges (=tree rotations) are 'compatible' with the flips of the monochromatic edges (=bitflips).
Pattern-avoiding binary trees and algorithms for their generation are discussed in that section.
The number of colorful triangulations of a convex $N$-gon is $2^q \cdot t_{q,3}=\frac{2^q}{2q+1} \binom{3q}{q}$ if $N=2q+2$ and $2^q\cdot t_{q,3}'=\frac{2^q}{q+1}\binom{3q+1}{q}$ if $N=2q+3$ ($q$ is the number of quadrangles obtained from removing the monochromatic edges), which are the sequences OEIS A153231 and OEIS A369510, respectively. The factor $2^q$ expresses the fact that with $q$ quadrangles, there are $2^q$ ways of placing the monochromatic edges, 2 choices in each quadrangle.