Question

Show that any binary search tree with n nodes can be transformed into any other search tree using O(n) rotations. Also show that you need at most n - 1 right rotations to transform a tree into a chain.

Answer 1

The idea is to construct an algorithm that converts any n-node binary tree into a left chain in time O(n) and then use the inverse of this algorithm to convert the obtained left chain into the desired binary tree.

Algorithm that converts any n-node binary tree into a left chain in time O(n).

Algorithm:

1. Perform left rotations on the root node until its right child is empty.
2. If the left child is now empty we are done. If the left child is not empty we traverse down to the left and go back to step 1 to perform rotations on this subtree.

Time:

There are n nodes in the binary tree. A rotation takes time O(1). Each time we do a rotation the height of the left chain that we are building grows with at least one. Therefore the algorithm will terminate after at most n rotations giving us time O(n).

Correctness:

The algorithm traverses down to the left doing rotations. It traverses down after making sure that the right child is empty. Therefore the above nodes are allways making up a left chain since we do not alter them after traversing downwards. When the algorithm finishes we clearly have a correct left chain.

Algorithm that converts a left chain into any n-node binary tree in time O(n).

Algorithm:

Looking at the above algorithm we can for each n-node binary tree define an algorithm that converts a left chain into this tree. Instead of left rotations we perform right rotations. We perform these rotations in reverse order.

Time:

Clearly O(n) (the same as the algorithm above).

Correctness:

Since the first algorithm is correct its inverse, defined in the way we have defined it, is also correct.

NOTE: As per Chegg policy, I am allowed to answer only 1 long question (including sub-parts) on a single post. Kindly post the remaining questions separately and I will try to answer them. Sorry for the inconvenience caused.