Generate binary trees

Generate various classes of binary trees with vertex set $\{1,2,\ldots,n\}$.
Number $n$ of vertices (max. 20; max. 10 for non-friendly patterns)
Forbidden patterns
Predefined inputs
Output format
Output  numbering graphics

Object info

We consider binary trees with vertex set $[n]:=\{1,\ldots,n\}$ whose vertex labels are given by the search tree property, i.e., for any vertex $i$, all vertices in the left subtree are smaller than $i$, and all vertices in the right subtree are larger than $i$. This allows encoding a binary tree $T$ with $n$ vertices as a permutation $\tau(T)$ of length $n$, by recording the vertices of $T$ in a preorder traversal, i.e., we first record the root of $T$, followed by recursively recording vertices in the left subtree of the root, followed by recursively recording vertices in the right subtree of the root. For the tree $T$ shown in the figure, the corresponding permutation is $\tau(T)=(6,5,2,1,3,4,8,7,9,10)$. It is well known that this mapping $\tau$ is a bijection between binary trees with vertex set $[n]$ and permutations of length $n$ that avoid the pattern $231$ (see pattern-avoiding permutations).

6 5 8 2 7 9 1 3 10 4 T

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:

If $T$ does not contain $(P,e)$, then we say that $T$ avoids $P$.

4 2 5 1 3 e(2)=0 e(5)=1 e(1)=0 e(3)=1 (P,e) 6 5 8 2 7 9 1 3 10 4 T contains (P,e)

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).

Enumeration (OEIS)

By avoiding certain tree patterns, we obtain classes of binary trees that are in bijection with a variety of other combinatorial objects, some of them classical. The corresponding OEIS sequences are listed below.

Download source code

[Zipped C++ source code (GNU GPL)]

References