3
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.