5 BST Transformations- (30 pts) In this problem you will prove that any arbitrary n-node binary search tree T can be transformed into any other arbitrary n-node binary search tree T2 using O(n) rotations. (a) Show that at most n - 1 right rotations suffice to transform any arbitrary n-node binary search tree into a right-going chain. To do this do the following (no partial credit if you skip one of the steps below, e.g., if you present just the algorithm but do not prove its correctness or how many rotations it performs): (i) Present an algorithm that performs the transformation (ii) Prove that your algorithm correctly transforms any arbitrary n-node BST into a right-going chain, and (ii) Prove that your algorithm performs at most n - 1 right rotations in the process (and no left- rotations). (b) Observe the relationship betweeen right rotations and left rotations and use it to show how to transform the right-going chain into any arbitrary BST T2 in at most n - 1 left rotations. (c) Conclude that the total number of rotations to transform an arbitrary n-node BST Ti into any other arbitrary n-node BST T2 is O(n)