Problem

You are given two non$-$empty binary search tree T$1$ and T$2.$ T$1$ and T$2$ store the same keys. The structure of

both trees, however, is different. Implement an algorithm that uses rotations on T$1$ to make it equivalent

to T$2.$ That is$,$ both trees should have identical structure. Note that you are only allowed to use rotations

and only on T$1$; you are not allowed to modify the trees in any other way. The implementation must be

iterative.

Implementation

You are given two files $($which you can download from canvas$)$: Lab$2.$java and BST$.$java. The file

Lab$2.$java generates test cases, performs the tests, and outputs the results. The file BST$.$java partially

implements a binary search tree and contains the function problem; implement your solution in that

function. Do not make any changes outside of that function; such changes will be undone. Do

not output anything to the terminal. The class BST also contains the functions rotateL, rotateR, find,

as well as functions for in$-$ and pre$-$order. Feel free to use these functions in your implementation.

The program already implemented in the file Lab$2$java randomly generates test cases. The seed of the

random number generator is set to ensure the same test cases whenever to program is executed. Note that

the purpose of the tests is for you to avoid major mistakes. Passing all given tests does not imply that

your algorithm is correct, especially that is has the expected runtime.