Generating Binary Trees Lexicographically

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