ON ROTATIONS AND THE GENERATION OF BINARY-TREES

The rotation graph, Gn, has vertex set consisting of all binary trees with n nodes. Two vertices are connected by an edge if a single rotation will transform one tree into the other. We provide a simpler proof of a result of Lucas that Gn, contains a Hamilton path. Our proof deals directly with the pointer representation of the binary tree. This proof provides the basis of an algorithm for generating all binary trees that can be implemented to run on a pointer machine and to use only constant time between the output of successive trees. Ranking and unranking algorithms are developed for the ordering of binary trees implied by the generation algorithm. These algorithms have time complexity O(n2) (arithmetic operations). We also show strong relationships amongst various representations of binary trees and amongst binary tree generation algorithms that have recently appeared in the literature. © 1993 Academic Press, Inc.