Please don't change anything else in the code only do implementing inside the function in bold below

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! }

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

return order; }

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

return order; } }

import java.io.*; import java.util.*; public class BST { * /** * Problem: Perform rotations on treel to make it equivalent to tree2. 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 ti to make it equivalent to T2. That * is, both tress should have identical structure. Note that you are only * allowed to use rotations and only on Tl; 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. | */ public static void problem (BST treel, BST tree2) { // Implement me! } import java.io.*; import java.util.*; public class BST { * /** * Problem: Perform rotations on treel to make it equivalent to tree2. 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 ti to make it equivalent to T2. That * is, both tress should have identical structure. Note that you are only * allowed to use rotations and only on Tl; 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. | */ public static void problem (BST treel, BST tree2) { // Implement me! }