title: Is it always possible to turn one BST into another using tree rotations?
body: <p>Given a set of values, it's possible for there to be many different possible binary search trees that can be formed from those values.  For example, for the values 1, 2, and 3, there are five BSTs we can make from those values:</p>
  
  <pre><code>1      1      2      3      3
   \      \    / \    /      /
    2      3  1   3  1      2
     \    /           \    /
      3  2             2  1
  </code></pre>
  
  <p>Many data structures that are based on balanced binary search trees use <strong><a href="http://en.wikipedia.org/wiki/Tree_rotation" rel="noreferrer">tree rotations</a></strong> as a primitive for reshaping a BST without breaking the required binary search tree invariants.  Tree rotations can be used to pull a node up above its parent, as shown here:</p>
  
  <pre><code>                rotate
           u      right           v
          / \     -----&gt;         / \
         v   C                  A   u
        / \       &lt;-----           / \
       A   B      rotate          B   C
                   left
  </code></pre>
  
  <p>Given a BST containing a set of values, is it always possible to convert that BST into any arbitrary other BST for the same set of values?  For example, could we convert between any of the five BSTs above into any of the other BSTs just by using tree rotations?</p>