P152: Enumeration of all rooted plane trees with exactly $n$ vertices and exactly $c$ leaves

P152: Enumeration of all rooted plane trees with exactly $n$ vertices and exactly $c$ leaves

Input:

An integer $n$.

Output:

All rooted plane trees with exactly $n$ vertices and exactly $c$ leaves .

Complexity:

$O(n-c)$ 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)