Constant Time Generation of Rooted Trees

Abstract

This paper generalizes a result of Ruskey [SIAM J. Comput., 7(1978), pp. 424–439] for generating k-ary trees lexicographically to generating all rooted trees with n vertices. An algorithm is presented which generates canonical representations of these trees in a well-defined order. As in other works, the average number of steps per tree is constant.