Generating Binary Trees by Transpositions

Frank Ruskey, Department of Computer Science, University of Victoria, Canada.
Andrzej Proskurowski, Department of Information and Computer Science, University of Oregon, USA.


Let T(n) denote the set of all bitstrings with n 1's and n 0's that satisfy the property that in every prefix the number of 0's does not exceed the number of 1's. This is a well known representation of binary trees. We consider algorithms for generating the elements of T(n) that satisfy one of the following constraints: (a) successive bitstrings differ by the transposition of two bits, or (b) successive bitstrings differ by the transposition of two adjacent bits. In case (a) a constant average time generation algorithm is presented. In case (b) we show that such generation is possible if and only if n is even or n < 5. A constant average time algorithm is presented in this case as well.

Selected papers that refer to this paper:

Back to Frank Ruskey's publication list.