Check whether it is possible to turn one BST into another using only right-rotations
If $T_1$ and $T_2$ don't encode the same sequence, they are not right-convertible into each other (obviously). This can be tested in linear time by inorder traversal of both trees.

The following procedure tests, if $T_1$ can be right-converted into $T_2$:


If both trees are empty, $T_1$ is right-convertible into $T_2$.
Right rotations move the root of the left subtree to the root of the complete tree. Thus, only nodes on the left flank of the tree can be rotated to the root. If the root node of $T_2$ is not on the left flank of $T_1$, $T_1$ is not right-convertible into $T_2$.
If the root $r_2$ of $T_2$ is on the left flank of $T_1$, obtain $T_1'$, by rotating $r_2$ up one level repeatedly, until $r_2$ is the root. Now $T_1$ is right-convertible into $T_2$, if and only if the left and right subtree of $T_1'$ are right-convertible into the left and right subtree of $T_2$, respectively.


Runtime:

Since each node will be rotaded up only once and by at most as many steps as the height of the tree, we need at most $O(n^2)$ rotations. If in $T_1$ all nodes are on the left flank and in $T_2$ all nodes are on the right flank, we will need $\frac {n(n-1)}2$ rotations, so the worst case runtime is in $\Theta(n^2)$.

Correctness:

If the algorithm finds a sequence of rotations, there obviously is one. To see the other direction, note the following:


If we rotate $r_2$ off the left flank, we immediately destroy right-convertability. So such rotations can never be necessary.
Any rotation not involving $r_2$ will affect a subtree, that is not changed by moving $r_2$ to the root. (It may be moved around as a whole, but this is independent of rotations within the subtree.) So if this rotation is necessary, we can still do it at a later time.


From these points correctness follows by structural induction.