# Unique keys in a binary search tree

I'm studying for my finals and I can across this statement.

"For a fixed set of (unique) keys, any binary search tree containing those keys can be converted to any other BST on the same set of keys via a sequence of left- and/or right- rotations."

I'm interested in a proof. Does anyone know any references?

• You can probably prove it by induction on the size of the tree. Have you tried? Apr 6 '14 at 19:13
• Alternatively, think about what happens if you just apply right rotations until none are possible. Which search tree do you end up at? Apr 6 '14 at 21:47

## 1 Answer

Here's a short method of transforming a BST $T_1$ into any other BST $T_2$ on the same set of keys, taken from notes written by Doug Hogan at Penn State:

Define the right spine of a BST as the root and all descendants of the root that are reachable by following only right pointers from the root. A right-linear chain is a BST that has all n nodes in the right spine.

Let $T'$ be the (unique) right-linear chain of $n$ keys. Let $r = (r_1, r_2, ..., r_k)$ be a sequence of right rotations that transforms $T_1$ into $T'$, and let $r' = (r'_1, r'_2, ...,r'_{k'})$ be a sequence of right rotations that transforms $T_2$ to $T'$. We know there exist sequences $r$ and $r'$ with $k, k' \leq n-1$, since a right rotation adds exactly one node to the right spine. For each right rotation $r'_i$ let $l'_i$ be the corresponding left rotation. Then, the sequence $(r_1, r_2, ..., r_k,l'_{k'},l'_{k'-1}, ..., l'_2, l'_1)$ transforms $T_1$ to $T_2$ in at most $2n-2$ rotations.

...and here's another explanation, which gives a nice recursive algorithm.

Google search terms: binary search tree transform rotation proof.