Generating regular k-ary trees efficiently

A recursive algorithm GenWordsR and a non-recursive algorithm GenWordsNR ar e presented in this paper to generate sequences for regular k-ary trees eff iciently. They are compared with same of the previous recursive and non-rec ursive algorithms for this problem that were found in the literature. When the average number of recursive calls is used as a measure of the time comp lexity of recursive algorithms for generating k-ary trees, O(k) calls for a k-ary tree is the best result in the previous recursive algorithms, while O(1/k) calls for a k-ary tree is needed by GenWordsR. When the average numb er of comparisons is used as a measure of the time complexity of non-recurs ive algorithms for generating k-ary trees, GenWordsNR outperforms the previ ous non-recursive algorithms. As k increases, the number (and the average n umber) of comparisons performed by GenWordsNR tends to 66% that of the best previous non-recursive algorithms.