BST Rotations to make one tree equal to the other

Question

I have this problem: You are given two non-empty binary search tree T1 and T2.T1 and T2 store the same keys. The structure of both trees, however, is different. Implement an algorithm that uses rotations on T1 to make it equivalent to T2. That is, both trees should have an identical structure. Note that you are only allowed to use rotations and only on T1; you are not allowed to modify the trees in any other way.

If anyone could help nudge me in the right direction of implementing this I would very much appreciate it. Here is the code so far.

import java.io.*;
import java.util.*;

public class BST
{
    /**
     *  Problem: Perform rotations on tree1 to make it equivalent to tree2.
     */
    public static void problem(BST tree1, BST tree2)
    {
        // Implement me!
        //Base Case
        if(tree1 == null && tree2 == null){
            return;
        }
    }

    // ---------------------------------------------------------------------
    // Do not change any of the code below!

    private class Node
    {
        public Node left = null;
        public Node right = null;
        public Node parent = null;

        public int key;

        public Node(int key)
        {
            this.key = key;
        }
    }

    private Node root = null;

    public int getRootKey()
    {
        return root.key;
    }

    private Node find(int key)
    {
        for (Node cur = root; cur != null;)
        {
            if (key < cur.key)
            {
                cur = cur.left;
            }
            else if (key == cur.key)
            {
                return cur;
            }
            else // key > cur.key
            {
                cur = cur.right;
            }
        }

        return null;
    }

    //     x            y
    //    / \          / \
    //   a   y   =>   x   c
    //      / \      / \
    //     b   c    a   b
    private void rotateL(Node xNode)
    {
        Node xPar = xNode.parent;
        boolean isRoot = xPar == null;
        boolean isLChild = !isRoot && xPar.left == xNode;

        Node yNode = xNode.right;
        Node beta = yNode.left;

        if (isRoot) root = yNode;
        else if (isLChild) xPar.left = yNode;
        else xPar.right = yNode;

        yNode.parent = xPar;
        yNode.left = xNode;

        xNode.parent = yNode;
        xNode.right = beta;

        if (beta != null) beta.parent = xNode;
    }

    //     y        x
    //    / \      / \
    //   x   c => a   y
    //  / \          / \
    // a   b        b   c
    private void rotateR(Node yNode)
    {
        Node yPar = yNode.parent;
        boolean isRoot = yPar == null;
        boolean isLChild = !isRoot && yPar.left == yNode;

        Node xNode = yNode.left;
        Node beta = xNode.right;

        if (isRoot) root = xNode;
        else if (isLChild) yPar.left = xNode;
        else yPar.right = xNode;

        xNode.parent = yPar;
        xNode.right = yNode;

        yNode.parent = xNode;
        yNode.left = beta;

        if (beta != null) beta.parent = yNode;
    }

    public void insert(int key)
    {
        if (root == null)
        {
            root = new Node(key);
            return;
        }

        Node par = null;

        for (Node node = root; node != null;)
        {
            par = node;

            if (key < node.key)
            {
                node = node.left;
            }
            else if (key > node.key)
            {
                node = node.right;
            }
            else // key == node.key
            {
                // Nothing to do, because no value to update.
                return;
            }
        }

        // Create node and set pointers.
        Node newNode = new Node(key);
        newNode.parent = par;

        if (key < par.key) par.left = newNode;
        else par.right = newNode;
    }

    public int[] getInOrder()
    {
        if (root == null) return new int[] { };

        Stack<Node> stack = new Stack<Node>();
        ArrayList<Integer> orderList = new ArrayList<Integer>();

        for (Node node = root;;)
        {
            if (node == null)
            {
                if (stack.empty()) break;

                node = stack.pop();
                orderList.add(node.key);
                node = node.right;
            }
            else
            {
                stack.push(node);
                node = node.left;
            }
        }

        int[] order = new int[orderList.size()];
        for (int i = 0; i < order.length; i++)
        {
            order[i] = orderList.get(i);
        }

        return order;
    }

    public int[] getPreOrder()
    {
        if (root == null) return new int[] { };

        Stack<Node> stack = new Stack<Node>();
        ArrayList<Integer> orderList = new ArrayList<Integer>();

        for (Node node = root;;)
        {
            if (node == null)
            {
                if (stack.empty()) break;

                node = stack.pop();
                node = node.right;
            }
            else
            {
                orderList.add(node.key);
                stack.push(node);
                node = node.left;
            }
        }

        int[] order = new int[orderList.size()];
        for (int i = 0; i < order.length; i++)
        {
            order[i] = orderList.get(i);
        }

        return order;
    }
}

And here is the code that tests the function of the other:

import java.io.*;
import java.util.*;

public class Lab1
{

    // ---------------------------------------------------------------------
    // Do not change any of the code below!

    private static final int LabNo = 4;
    private static final String quarter = "Fall 2020";
    private static final Random rng = new Random(190718);

    private static boolean testProblem(int[][] testCase)
    {
        int[] arr1 = testCase[0];
        int[] arr2 = testCase[1];

        // --- Build tree ---

        BST tree1 = new BST();
        BST tree2 = new BST();

        for (int i = 0; i < arr1.length; i++)
        {
            tree1.insert(arr1[i]);
            tree2.insert(arr2[i]);
        }

        int[] pre2 = tree2.getPreOrder();


        BST.problem(tree1, tree2);


        // --- Verify tree. ---

        int[] pre1 = tree1.getPreOrder();
        int[] in1 = tree1.getInOrder();

        if (in1.length != arr1.length) return false;

        for (int i = 0; i < in1.length; i++)
        {
            if (in1[i] != i) return false;
            if (pre1[i] != pre2[i]) return false;
        }

        return true;
    }

    public static void main(String args[])
    {
        System.out.println("CS 302 -- " + quarter + " -- Lab " + LabNo);
        testProblems(1);
    }

    private static void testProblems(int prob)
    {
        int noOfLines = 100000;

        System.out.println("-- -- -- -- --");
        System.out.println(noOfLines + " test cases for problem " + prob + ".");

        boolean passedAll = true;
long start = System.currentTimeMillis();
        for (int i = 1; i <= noOfLines; i++)
        {
            boolean passed = false;
            boolean exce = false;

            try
            {
                int[][] testCase = createProblem(i);
                passed = testProblem(testCase);
            }
            catch (Exception ex)
            {
                passed = false;
                exce = true;
            }

            if (!passed)
            {
                System.out.println("Test " + i + " failed!" + (exce ? " (Exception)" : ""));
                passedAll = false;
                break;
            }
        }
System.out.println((System.currentTimeMillis() - start) + " ms");
        if (passedAll)
        {
            System.out.println("All test passed.");
        }

    }

    private static void shuffle(int[] arr)
    {
        for (int i = 0; i < arr.length - 1; i++)
        {
            int rndInd = rng.nextInt(arr.length - i) + i;
            int tmp = arr[i];
            arr[i] = arr[rndInd];
            arr[rndInd] = tmp;
        }
    }

    private static int[][] createProblem(int testNo)
    {
        int size = rng.nextInt(Math.min(200, testNo)) + 1;

        int[] numbers1 = new int[size];
        int[] numbers2 = new int[size];

        for (int i = 0; i < size; i++)
        {
            numbers1[i] = i;
            numbers2[i] = i;
        }

        shuffle(numbers1);
        shuffle(numbers2);

        return new int[][] { numbers1, numbers2 };
    }
}

Answer 1

//I understand this is quite late but this is more for people who look now for this help

public static void problem(BST tree1, BST tree2)
{
    //if root is null then we've reached the end of a branch (base case)
    if(tree1.root == null || tree2.root == null)
    {
        return;
    }

    //finding the node we need to rotate to tree1's root to match 2nd tree
    Node match = tree1.find(tree2.getRootKey());

    //loop to rotate matched node until it becomes tree1's new root or parent of the root
    while(match != tree1.root && match != tree1.root.parent)
    {
        //parent node of matched node we need to get to new position
        Node matchParent = match.parent;

        //move matched node we want up the levels of tree1
        //if matched node key is more than its parent then rotate parent left (which moves matched node up a level)
        //otherwise rotate the parent right (still moves matched node up a level)
        if(match.key > matchParent.key)
        {
            tree1.rotateL(matchParent);
        }
        else
        {
            tree1.rotateR(matchParent);
        }
    }

    //if the matched node becomes the parent of tree1's root, in the loop above, then we need to
    //change it so that the matched node is the root to line up with tree2
    if(match == tree1.root.parent)
    {
        tree1.root = match;
    }

    // recursively go through left tree
    // new BSTs to signify left subtrees
    BST leftTree1 = new BST();
    BST leftTree2 = new BST();

    leftTree1.root = tree1.root.left;
    leftTree2.root = tree2.root.left;
    problem(leftTree1, leftTree2);

    // recursively go through right tree
    // new BSTs to signify right subtrees
    BST rightTree1 = new BST();
    BST rightTree2 = new BST();

    rightTree1.root = tree1.root.right;
    rightTree2.root = tree2.root.right;
    problem(rightTree1, rightTree2);
}