The Combinatorial Object Server

Number $n$ of vertices | (max. 20; max. 10 for non-friendly patterns) | |

Forbidden patterns | ||

Predefined inputs | ||

Output format | ||

Output
numbering
graphics

We consider binary trees with vertex set $[n]:=\{1,\ldots,n\}$ whose vertex labels are given by the search tree propery, 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).

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:

- For every edge $(i,p(i))$ of $P$ with $e(i)=1$ (drawn solid in the figure below), we have that $f(i)$ is a child of $f(p(i))$ in $T$. Specifically, if $i$ is the left child of $p(i)$, then $f(i)$ is the left child of $f(p(i))$, whereas if $i$ is the right child of $p(i)$ then $f(i)$ is the right child of $f(p(i))$.
- For every edge $(i,p(i))$ of $P$ with $e(i)=0$ (drawn dashed in the figure below), we have that $f(i)$ is a descendant of $f(p(i))$ in $T$. Specifically, if $i$ is the left child of $p(i)$, then $f(i)$ is a left descendant of $f(p(i))$, whereas if $i$ is the right child of $p(i)$ then $f(i)$ is a right descendant of $f(p(i))$.

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

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.

- none: OEIS A000108 (Catalan numbers)
- 123,01 / 132,11 / 213,11: OEIS A000079 (powers of 2)
- 123,11: OEIS A001006 (Motzkin numbers)
- 1234,001 / 1243,011 / 1324,011 / 1423,011 / 1432,101 / 2134,101 / 2143,101: OEIS A001519
- 1234,011 / 1432,111: OEIS A005773
- 1234,101 / 1243,111 / 1324,111 / 1423,111 / 2134,111 / 2143,111: OEIS A025242
- 12345,0001: OEIS A007051
- 12345,0011: OEIS A054391
- 12345,0111: OEIS A159772
- 12345,1001: OEIS A176677
- 12345,1101: OEIS A159768
- 12345,1111: OEIS A036766
- 12534,1111: OEIS A159769
- 12543,1111: OEIS A159770
- 13254,1111: OEIS A159771
- 21354,1111: OEIS A159773
- 12345,0101 / 12354,0111 / 12435,0111 / 12534, 0111 / 13245,0111 / 13254,0111 / 14235,0111 / 14325,0111 / 15243,0111 / 15324,0111 / 15423,0111 / 15423,1101 / 15432,1101: OEIS A365508
- 12345,1011 / 12543,1011: OEIS A365509
- 13245,1101 / 13254,1101 / 15234,1101 / 15243,1101 / 21345,1101 / 21354,1101: OEIS A365510

- [DPTW12] M. Dairyko, L. Pudwell, S. Tyner, and C. Wynn. Non-contiguous pattern avoidance in binary trees. Electron. J. Combin., 19(3):Paper 22, 21 pp., 2012.
- [GMN23] P. Gregor, T. Mütze, and Namrata. Combinatorial generation via permutation languages. VI. Binary trees. arXiv:2306.08420, Jun 2023.
- [LRvBR93] J. M. Lucas, D. Roelants van Baronaigien, and F. Ruskey. On rotations and the generation of binary trees. J. Algorithms, 15(3):343–366, 1993.
- [Row10] E. S. Rowland. Pattern avoidance in binary trees. J. Combin. Theory Ser. A, 117(6):741–758, 2010.
- [Wil13] A. Williams. The greedy Gray code algorithm. In Algorithms and data structures, volume 8037 of Lecture Notes in Comput. Sci., pages 525–536. Springer, Heidelberg, 2013.