Generation of t-ary trees with Ballot-sequences^*

Abstract

We define Ballot-sequences for t-ary trees based on the ideas of Ballot-sequences of binary trees presented by Rotem. Later an efficient algorithm for the generation of t-ary trees with Ballot-sequences in B-order is presented. The algorithm generates each sequence in constant average time O(1), and the sequences are generated in lexicographical order. The ranking and unranking algorithms with O(tn) time complexity are also described.

Keywords:

• t-ary tree
• Recursion
• Ballot-sequences
• P-sequences

Acknowledgments

The authors would like to thank the anonymous referee for making helpful suggestions.

Notes

^*This research was supported by University of Tehran

^‡[email protected]