Physical Sciences and Mathematics Commons^™

Finding Paths In The Rotation Graph Of Binary Trees, Rodney O. Rogers

Retrospective Theses and Dissertations

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 R_n 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 …