Generating Binary Trees Lexicographically

Authors:
  • FRF. Ruskey
    F. Ruskey
  • THT. C. Hu
    T. C. Hu

Abstract
We represent a binary tree by the level numbers of its leaves from left to right. Thus every binary tree of n leaves corresponds to a sequence of n numbers. We first give the necessary and sufficient conditions for a sequence to represent a binary tree; then we give an algorithm for generating all the feasible sequences lexicographically as a list. Also, algorithms are developed to determine the position of a given sequence, or to generate the sequence of a given position. Finally, it is shown that the average time per sequence generated is constant (independent of the length of the sequence).

This publication has 1 reference indexed in Scilit: