Efficient Enumeration of Ordered Trees with k Leaves

摘要

In this paper, we give 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 for each, while our algorithm generates such trees in O(1) time for each in worst case.