Efficient enumeration of ordered trees with k leaves

This paper presents a simple algorithm to generate all ordered trees with exactly n vertices including exactly k leaves. The best known algorithm generates such trees in O(n−k) time per tree, whereas our algorithm generates such trees in O(1) time per tree in the worst case.