P150: Enumeration of all rooted plane trees with exactly $n$ vertices

P150: Enumeration of all rooted plane trees with exactly $n$ vertices

Input:

An integer $n$.

Output:

All rooted plane trees with exactly $n$ vertices.

Complexity:

$O(1)$ time per tree with $O(n)$ space.

Comment:

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

Reference:

[Nakano2002] (Bibtex)