Menu
An efficient method for generating level sequence representations of rooted trees in a well-defined order was developed by Beyer and Hedetniemi. In this paper, we extend Beyer and Hedetniemi’s approach to produce an algorithm for parallel generation of rooted trees. This is accomplished by defining the lexicographic distance between two rooted trees to be the number of rooted trees between them in the ordering of trees produced by the Beyer and Hedetniemi algorithm. Formulas are provided for the lexicographic distance between rooted trees with certain structures. In addition, we present algorithms for ranking and unranking rooted trees based on the ordering of the trees that is induced by the Beyer and Hedetniemi generation algorithm.