[Solved]: Check whether it is possible to turn one BST into another using only right-rotations

ignougroup
Problem Detail: Given two binary search trees T1 and T2, if it is possible to obtain T2 from T1 using only right-rotation, we say that T1 can be right-converted to T2. For example, given three binary search tree T1, T2 and T3: For example, given three binary search tree T1, T2 and T3: 

 Tree 1                Tree 2              Tree 3     a                    b                   a    /                    /                  /   b                    d   a               d   /                       /                  d   c                    c                   b                                                                                               c

T2 can be right-converted from T1, T3 can be right-converted from T1. But T3 cannot be right-converted from T2, T2 cannot be right-converted from T3. Given two arbitrary BST, how to determine whether they are right-convertible with respect to each other?

Asked By : leonidas1573

Answered By : FrankW

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29281