| Number $n$ of vertices | (max. 20; max. 10 for non-friendly patterns) | |
| Forbidden patterns | ||
| Predefined inputs | ||
| Output format | ||
There are two natural notions of pattern containment in binary trees [Row10, DPTW12]. A tree pattern is a pair $(P,e)$, where $P$ is a binary tree with vertex set $[k]$, and $e$ is a mapping that assigns to every non-root vertex $i$ of $P$ a number $e(i)\in \{0,1\}$, and the value $e(i)$ determines how the relationship between $i$ and its parent vertex $p(i)$ in $P$ translates into an occurrence of the pattern $P$ in a host tree $T$ with vertex set $[n]$. Formally, we say that $T$ contains $P$, if there is an injection $f:[k]\rightarrow [n]$ of the vertices of $P$ into the vertices of $T$ satisfying the following conditions:
The figure shows an occurrence of the pattern $(P,e)$ in the tree $T$ from before. On the other hand, $T$ avoids the pattern $(P,e')$ that is obtained from modifying $(P,e)$ by changing $e(2)=0$ to $e'(2):=1$ (i.e., the edge $(2,4)$ in $P$ is solid instead of dashed).
The algorithm running on this website generates all binary trees with $n$ vertices avoiding certain tree patterns (possibly none). Each pattern $(P,e)$ is specified by the preorder permutation $\tau(P)$ of length $n$, and the 0/1-string of length $n-1$ of all $e$-values of the non-root vertices of $P$, in the order of the preorder permutation $\tau(P)$, separated by comma. For example, the pattern $(P,e)$ from before is encoded as $\tau(P),e(2)e(1)e(3)e(5)=42135,0011$. Multiple patterns are separated by semicolon. In graphical output mode, each generated binary tree $T$ is printed as a bracketing expression $\beta(T)$, defined recursively as $\beta(T):=$[$\beta(L(T))$,$\beta(R(T))$], where $L(T)$ and $R(T)$ are the left and right subtree of the root of $T$. In textual output mode, $T$ is printed as the preorder permutation $\tau(T)$. The tree $T$ in the figure above is printed as $\beta(T)=$[[[[ , ],[ ,[ , ]]], ],[[ , ],[ ,[ , ]]]] and $\tau(T)=6\,5\,2\,1\,3\,4\,8\,7\,9\,10$.
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. The paper [GMN23] proposes a generalization of Williams' algorithm, which allows specifying certain forbidden tree patterns that satisfy some mild constraints. A pattern satisfying these constraints is called friendly (see the paper for definitions). If all specified tree patterns are friendly, then our generator uses the algorithm from [GMN23], and otherwise the trees are generated by a brute-force method (with a stricter limit on the number of vertices $n$, which can be disabled in the downloaded source code).