Generating <i>t</i>-Ary Trees Lexicographically

Abstract

This paper extends the results of Ruskey and Hu (1977) from binary trees to t-ary trees. A t-ary tree on N leaves is represented by the sequence of N level numbers of the leaves of that tree. An algorithm is presented for generating these sequences lexicographically as a list. This algorithm is shown to have an average running time of $O(t)$ per sequence generated. $O(N)$ algorithms are developed for determining the position (ranking) of a sequence in the list, and for producing the sequence corresponding to a given place in the list (unranking). Also, a one-to-one correspondence between t-ary trees and walks on a certain lattice is demonstrated; as well as a close relationship between these walks and the lexicographic ranking.