Show that any arbitrary \(n\)-node binary search tree can be transformed into any other arbitrary \(n\)-node binary search tree using \(O(n)\) rotations. (Hint: First show that at most \(n - 1\) right rotations suffice to transform the tree into a right-going chain)

First of all, it is helpful to note that a rotation can be undone by applying another rotation of the other type to the same two nodes in the resulting binary search tree. In other words, saying tree \(T_1\) can be transformed into tree \(T_2\) by some sequence of rotations implies that \(T_2\) can be transformed into \(T_1\) by the inverse sequence of rotations.

As per the hint, we can transform any binary search tree into a right-going chain as follows: The root node and all its right children will form the base of our chain. Each node that is a left child of some node within our chain can be brought into the chain by way of a right rotation. This rotation may result in new left child nodes off the right chain and so we simply repeat this process until all nodes have been included in the right-going chain. This transformative action takes at most \(n-1\) transofmrations (the wors-case being when our root node has no right child) and so we can change an binary search tree into a right-going chain in \(O(n)\) time.

Based on the conclusion of the first paragraph of this solution, this also means that we can transform a right-going chain into any valid binary search tree with the same collection of nodes in at most \(n - 1\) rotations. By combining these two steps, we are then able to transform one arbitrary \(n\)-node binary search tree into another by first converting it to a right-going chain and then converting that chain into our desired tree. Thest two steps together take at most \(2n - 2\) rotations and so we can accomplish such a transformation in \(O(n)\) time.