I need help with an iterative implementation to this problem. It is coded in Java and only needs the method problem implemented with no other helper methods.

Other times this question has been posted it had only been done recursively.

Here are the two other files with supporting code for this assignment Lab1.java and BST.java:

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

public class Lab1 {

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

private static final int LabNo = 1; 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

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

return true; }

public static void main(String args[]) { System.out.println("CS 302 -- 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

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

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

shuffle(numbers1); shuffle(numbers2);

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

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) { // Non-recursive implementation here }

// --------------------------------------------------------------------- // 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.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.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

public int[] getInOrder() { if (root == null) return new int[] { }; Stack stack = new Stack(); ArrayList orderList = new ArrayList(); 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

public int[] getPreOrder() { if (root == null) return new int[] { }; Stack stack = new Stack(); ArrayList orderList = new ArrayList(); 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 Problem You are given two non-empty binary search tree T and Ty. Tand T, store the same keys. The structure of both trees, however, is different. Implement an algorithm that uses rotations on T, to make it equivalent to Tg. That is, both trees should have identical structure. Note that you are only allowed to use rotations and only on T; you are not allowed to modify the trees in any other way. There is no strict overall runtime for this assignment. You should still try to keep it as low as possible. Very slow implementations will still result in a loss of points. Implementation You are given two files (which you can download from canvas): Lab1.java and BST.java. The file Lab1.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, rotate, 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 Lab1.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