Generating binary trees using rotations
David Zerling · Journal of the ACM · 1985
A new algorithm that, for the first time, exploits the rotational geometry of binary trees is developed in order to allow for the lexicographic generation of computer representations of these trees in average time O (1) per tree. “Rotation” codewords for these trees (in average time O (1) per tree) are also generated. It is shown how these codewords relate to lattice paths, and, using this relationship, that n ( n - 1)/( n + 2) is the average number of rotations needed to generate a binary tree on n nodes. Finally, a necessary and sufficient condition that a codeword represent a full binary tree (each node has 0 or 2 sons) on n = 2 m + 1 nodes is given and how to contract this codeword to obtain the codeword for the binary tree on m nodes for which this full tree is the extended binary tree is shown.