Summary
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).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Beyer, T., Hedetniemi, S.M.: Constant time generation of rooted trees. SIAM J. Comput. 9, 706–712 (1980)
Gupta, U.I., Lee, D.T., Wong, C.K.: Ranking and unranking of 2–3 trees. SIAM J. Comput. 11, 582–590 (1982)
Gupta, U.I., Lee, D.T., Wong, C.K.: Ranking and unranking of B-trees, J. Algorithms 4, 11–60 (1983)
Flajolet, P., Odlyzko, A.: Limit distributions for coefficients of iterates of polynomials with applications to combinatorial enumerations. (AT & T Bell Laboratories (1983) unpublished)
Knott, G.D.: A numbering system for binary trees. Commun. ACM 20, 113–115 (1977)
Proskurowski, A.: On the generation of binary trees, J. ACM 27, 1–2 (1980)
Rotem, D., Varol, Y.L.: Generation of binary trees from ballot sequences, J. ACM 25, 396–404 (1978)
Ruskey, F.: Generating t-ary trees lexicographically, SIAM J. Comput. 7, 424–439 (1978)
Ruskey, F., Hu, T.C.: Generating binary trees lexicographically. SIAM J. Comput. 6, 745–758 (1977)
Solomon, M., Finkel, R.A.: A note on enumerating binary trees. J. ACM 27, 3–5 (1980)
Trojanowski, A.E.: Ranking and listing algorithms for k-ary trees. SIAM J. Comput. 7, 492–509 (1978)
Wilf, H.S.: A unified setting for sequencing, ranking and selection algorithms for combinatorial objects. Adv. Math. 24, 281–291 (1977)
Williamson, S.G.: On the ordering, ranking and random generation of basic combinatorial sets, in Combinatoire et representation du groupe symetrique. Strasbourg: 1976
Zaks, S.: Lexicographic generation of ordered trees. Theor. Comput. Sci. 10, 63–82 (1980)
Zaks, S., Richards, D.: Generating trees and other combinatorial objects lexicographically. SIAM J. Comput. 8, 73–81 (1979)
Zaks, S.: Generation and ranking of k-ary trees, Inf. Process. Lett. 14, 44–48 (1982)
Author information
Authors and Affiliations
Additional information
Supported in part by National Science Foundation under Grants MCS 8342682 and ECS 8340031
Rights and permissions
About this article
Cite this article
Lee, C.C., Lee, D.T. & Wong, C.K. Generating binary trees of bounded height. Acta Informatica 23, 529–544 (1986). https://doi.org/10.1007/BF00288468
Received:
Issue date:
DOI: https://doi.org/10.1007/BF00288468