Generate plane trees

A free plane tree is a tree in which the neighbors of each vertex have a specified cyclic ordering. We think of this ordering as the cyclic ordering in which the neighbors appear around each vertex in an embedding of the tree in the plane. A rooted plane tree has in addition a marked vertex called the root.

The algorithm for tree generation running on this website is described in Sawada's paper [Saw06]. In graphical output, the trees are drawn as rooted trees with the root on the left and the children growing to the right. The root of rooted plane trees is highlighed red, and for free plane trees an arbitrary vertex is picked as the root (not highlighted). In textual output, each tree is printed in level representation, i.e., the sequence obtained by traversing the tree in pre-order, and recording the depth (=distance from the root) of each vertex. All trees with $n=5$ vertices are shown in the following figure.

	1	2	3	4	5	6	7	8	9	10
level sequence	01111	01112	01122	01123	01212	01222	01223	01232	01233	01234
rooted
free			=2	=5		=1	=2	=2	=2	=5

The number of rooted plane trees and free plane trees is given by OEIS A003239 and OEIS A002995, respectively.

[Zipped C source code (GNU GPL)]

• [Saw06] J. Sawada. Generating rooted and free plane trees. ACM Trans. Algorithms, 2(1):1–13, 2006.