Generating binary trees of bounded height

Chung Chieh Lee*, D. T. Lee, C. K. Wong

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

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).

Original languageEnglish (US)
Pages (from-to)529-544
Number of pages16
JournalActa Informatica
Volume23
Issue number5
DOIs
StatePublished - Sep 1 1986

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Generating binary trees of bounded height'. Together they form a unique fingerprint.

Cite this