Generating Binary Trees by Rotations
Joan
M. Lucas, Department of Computer Science,
SUNY Brockport, USA.
Dominique
Roelants van Baronagien, Department of Computer Science,
University of Victoria, Canada.
Frank
Ruskey, Department of Computer Science,
University of Victoria, Canada.
Abstract:
The rotation graph, G(n),
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 [x] that G(n)
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(n^{2})
(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.
 The postscript file is 269,994 bytes,
the dvi file is 80,500 bytes.
 Appeared in Journal of Algorithms, 15 (1993) 343366.
 An implementation is available.
 The algorithms are used in the
"
Object Server", in the
trees  Binary trees by rotations section.
 The reference Lucas [x] is to the paper:
Joan M. Lucas, The Rotation Graph is Hamiltonian, Journal
of Algorithms, 9 (1988) 503535.
 Typos:
 Page 356, Table 1, heading AlgM:
A [
should be {.
 Page 358, Figure 10, rightmost node in the tree:
The label 004
should be 104.
 This algorithm is presented in Section 7.2.1.6 of
The Art of Computer Programming by Donald Knuth.
Selected citations to this paper

JiaJie Liu1, William ChungKung Yen, and YenJu Chen,
An Optimal Algorithm for Untangling Binary Trees via Rotations,
The Computer Journal, 54 (2011) 18381844.

Patrick Dehornoy,
On the rotation distance between binary trees,
Advances in Mathematics, 223 (2010) 13161355.

D. Saha and S. SurKolay,
Encoding of Floorplans through Deterministic Perturbation,
22nd International Conference on VLSI Design, 2009.

Jean Pallo,
Generating binary trees by Glivenko classes on Tamari lattices,
Information Processing Letters,
Volume 85 , Issue 5 (March 2003) Pages: 235  238

William D. May and John C. Wierman,
Algorithms for Noncrossing Partitons,
Combinatorics, Probability and Computing,
Volume ??, (200?)
Pages: ??????.

F Hurtado, M Noy, J Urrutia,
Flipping Edges in Triangulations,
Discrete and Computational Geometry,
Volume 22, Number 3,
October 1999,
Pages: 333  346.

S. Bacchelli, E. Barcucci, E. Grazzini, and E. Pergola,
Exhaustive generation of combinatorial objects by ECO,
Acta Informatica,
Volume 40, Number 8,
July 2004,
Pages: 585  602.

Yangjun Chen,
A Systematic Method for Query Evaluation in
Distributed Heterogeneous Databases,
Journal of Information Science and Engineering,
16 (2000) 463497.

J.F. Korsh and P. LaFollette,
Multiset Permutations and Loopless Generation of
Ordered Trees with Specified Degree Sequence,
Journal of Algorithms, 34 (2000) 309336.

Conrado Martinez and Xavier Molinero,
A generic approach for the unranking of labeled
combinatorial classes,
Random Structures and Algorithms,
19 (2001) 472497.

Selim G. Akl and Ivan Stojmenovik,
Generating tary trees in parallel,
Nordic Journal of Computing, 3 (1996) 6371.

Chandra N. Sekharan, John G. Del Greco and Sailesh Rathi,
SpaceTime Tradeoffs in the Relative Unranking of
Binary Trees,
The Computer Journal, 39 (1996) 3944.