Transforming a Binary Tree Via Rotations

We examine an interesting fact: Given two different binary search trees on a given set of n keys, it is always possible to transform one tree into theother, using only a sequence of rotations. In fact, it can be shown that it is always possible to do this transformation using O(n) rotations. Our goal in this lab is to get some empirical justification of this claim, by experimenting with it on several examples.

In this applet, you will find two distinct binary search trees drawn below. Each such tree is drawn with the convention that internal nodes contain keys, and that external nodes are sentinels, displayed as black squares.

Initially, both of the trees are randomly created using the same underlying set of keys. You are not allowed to modify the first tree. Your goal is to transform the second tree using rotations until it looks identical to the first tree. In particular,if you click the mouse on any internal node of the second tree (other than the root),it will perform a rotation involving this node and its parent.

Try it out. See if you can match a given tree containing 8 internal nodes? What about with 16 internal nodes? Is there a method to the madness? Do you think you can quantify the number of rotations you use in the worst-case for a tree with n nodes?

Michael Goldwasser