P153: Enumeration of all plane trees with exactly $n$ vertices

P153: Enumeration of all plane trees with exactly $n$ vertices

Input:

An integer $n$.

Output:

All plane trees with exactly $n$ vertices.

Complexity:

$O(n^3)$ time per tree with $O(n)$ space.

Comment:

A \textit{plane tree} is a tree with a left-to-right ordering specified for the children of each vertex.

Reference:

[Nakano2002] (Bibtex)