Efficient loopless generation of Gray codes for k-ary trees

Vajnovszki recently developed a loopless algorithm [Inform. Process. Lett. 68 (1998) 113] to enumerate Gray codes for binary trees, and then Korsh and Lafollette gave a loopless algorithm [Inform. Process. Lett 70 (1999) 7] t o generate Gray codes for k-ary trees. In this paper, another loopless algo rithm is presented to list Gray codes for k-ary trees more efficiently in b oth space and time than the two former algorithms, and the algorithm is als o conceptually simpler than the predecessors. Based on the algorithm, Gray codes for k-ary trees with n internal nodes (n greater than or equal to 2 a nd k > 3) can be generated in at least 2(2(n-1)) different ways easily. (C) 2000 Elsevier Science B.V. All rights reserved.