#### Abstract

A binary tree coding scheme is a bijection mapping a set of binary trees to a set of integer tuples called codewords. One problem considered in the literature is that of listing the codewords for n-node binary trees, such that successive codewords represent trees differing by a single rotation, a standard operation for rebalancing binary search trees. Then, the codeword sequence corresponds to an Hamiltonian path in the rotation graph Rn of binary trees, where each node is labelled with an n-node binary tree, and an edge connects two nodes when their trees differ by a single rotation. A related problem is finding a shortest path between two nodes in Rn, which reduces to the problem of transforming one binary tree into another using a minimum number of rotations. Yet a third problem is determining properties of the rotation graph. Our work addresses these three problems.

#### Graduation Date

1996

#### Semester

Summer

#### Advisor

Dutton, Ronald;

#### Degree

Doctor of Philosophy (Ph.D.)

#### College

College of Arts and Sciences

#### Department

Department of Computer Science

#### Degree Program

Computer Science

#### Format

#### Language

English

#### Rights

Written permission granted by copyright holder to the University of Central Florida Libraries to digitize and distribute for nonprofit, educational purposes.

#### Length of Campus-only Access

None

#### Access Status

Doctoral Dissertation (Open Access)

#### Identifier

DP0000193

#### STARS Citation

Rogers, Rodney O., "Finding paths in the rotation graph of binary trees" (1996). *Retrospective Theses and Dissertations*. 3063.

http://stars.library.ucf.edu/rtd/3063