Generating binary trees of bounded height

Abstract

We present a new encoding scheme for binary trees with n internal nodes whose heights are bounded by a given value h, h≧⌈log2(n +1)1⌉. The scheme encodes the internal nodes of the tree level by level and enables us to develop an algorithm for generating all binary trees within this class in a certain predetermined order. Specifically, the trees are generated in decreasing height and for trees of the same height they are generated in lexicographically increasing order. The algorithm can be easily generalized to encompass t-ary trees with bounded height. It is then shown that the average generation time per tree is constant (independent of n and h). © 1986 Springer-Verlag.