import java.util.ArrayList;

enum TREETYPE {BST, AVL, SPLAY};

public class WirelessPower {
public int DEFAULT_HEIGHT = 0;
public int DEFAULT_ID = 0;
public int MINID = 10000;
public int MAXID = 99999;
public int MINLAT = -90;
public int MAXLAT = 90;
public int MINLONG = -180;
public int MAXLONG = 180;


/** 
 * The constructor performs the required initializations. It creates an empty object. It also 
 * specifies the type of the tree. The tree can be a regular BST which does not perform any 
 * re-structuring. It can be an AVL tree which re-balances the tree after every insertion or removal. 
 * The third type is a Splay tree which splays the accessed node to the tree root.
 * @param type one of the enumerators ot TREETYPE
 */
public WirelessPower(TREETYPE type) {
   this.m_type = type; // Initalize m_type to type of tree 
    m_root = null; // Initalzing root of the tree to null 
}

/**
 * @return the enumerated type of TREETYPE
 */
TREETYPE getType() {

    return m_type; // returning the type of tree.
}

/**
 * Copy constructor for WirelessPower
 */
public WirelessPower(WirelessPower rhs) {
    //Copying the type of tree
    m_type = rhs.m_type; 
    //Deep copy of the tree.
    m_root = copyOfTree(rhs.m_root);
}

/**
 * This function inserts a Customer object into the tree in the proper position. 
 * The Customer::m_id should be used as the key to traverse the WirelessPower tree 
 * and abide by BST traversal rules. The comparison operators (>, <, ==, !=) work with 
 * the int type in C++. A Customer id is a unique number in the range MINID - MAXID. 
 * We do not allow a duplicate id or an object with invalid id in the tree.
 * Note:
 * •        In the WirelessPower tree data structure every node is a Customer object which is 
 *      represented as a pointer to the Customer object. Therefore, for every insertion we 
 *      need to allocate memory and use the information of customer to initialize the new node. 
 *      Memory allocation takes place in the WirelessPower class.
 * •        If the tree type is BST, after an insertion, we should update the height for all nodes 
 *      in the insertion path.
 * •        If the tree type is AVL, after an insertion, we should update the height of each node in 
 *      the insertion path as well as check for an imbalance at each node in this path.
 * •        If the tree type is SPLAY, after and insertion, we need to splay the inserted node 
 *      and bring it to the root of the tree while the tree preserves the BST property as well as updating the node heights.
 */
// aCustomer here is the ID..
public void insert(Customer aCustomer) {

   //ArrayList to keep Track of nodes.
   ArrayList<Customer> tempNodes = new ArrayList<>();

    // Check for valid range of ID
    if (aCustomer.getID() < MINID || aCustomer.getID() > MAXID) {
        return;
    }

    // Check if tree is empty 
    if (isEmpty()) {
        // Create a new customer node and set it as the root since tree is empty
        m_root = new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude());

        return;
    }
    // To determine which type of insertion to use / rebalance as well
    switch (getType()) {
        case BST:
            m_root = insertBST(m_root, aCustomer,tempNodes);
            balance(tempNodes);
            break;
        case AVL:
            m_root = insertAVL(m_root, aCustomer,tempNodes);
            balance(tempNodes);
            break;
        case SPLAY:
           // m_root = insertBST(m_root, aCustomer);
            m_root = splay(m_root, aCustomer);
            break;
    }
}

/**
 * The clear function makes it an empty tree.
 */
public void clear() {
   m_root = null;
}

/**
 * The remove function traverses the tree to find a node with the id and removes 
 * it from the tree. In the case of BST or AVL tree the remove function should also update 
 * the heights for all nodes in the removal path. If the tree type is SPLAY, the remove 
 * function does not remove the node.
 */
public void remove(int id) {
    ArrayList<Customer> tempNodes = new ArrayList<>();

    switch (getType()) {
        case BST:
            m_root = deleteRecursively(m_root, id,tempNodes);

            break;
        case AVL:
            m_root = deleteRecursively(m_root, id,tempNodes);

            break;
        case SPLAY:
            //Do nothing if SPLAY tree
            break;
    }
}

/**
 * This function sets the type of an existing WirelessPower object. Once the type is changed, 
 * the function should re-structure the tree according to the following rules:
 * •        If the type is changed from BST or SPLAY to AVL, the function should reconstruct the 
 *      tree as an AVL tree. In the case of reconstruction the nodes are transferred from the 
 *      old tree to the new tree. There should not be any reallocation of memory.
 * •        If the type is changed from AVL to BST or Splay, there is no need for reconstruction. 
 *      After change the tree operations will perform according to the new type.
 * •        Any change between BST and SPLAY types will not trigger a reconstruction. After 
 *      change the tree operations will perform according to the new type.
 */
public void setType(TREETYPE type) {
    //If the new type is the same as current just return
    //Nothing to do.
    if(m_type == type) {
        return;
    }

    switch(m_type) {
        //AVL doesn't need to be reconstructed to BST or SPLAY
        case AVL:
        //Just update the variable to tree type instead.
        if (type == TREETYPE.BST || type == TREETYPE.SPLAY) {
            m_type =type; // Update the type
        }
        break;
        case BST:
            if(type == TREETYPE.AVL){
                BstToAVL();
                m_type = type;
            } else {
                m_type = type;
            }
        break;
        case SPLAY:
            if(type == TREETYPE.AVL) {
                BstToAVL();
                m_type = type;
            }
        break;
        default:
        break;
    }
}

/**
 * creates an exact deep copy of the rhs.
 */
public Customer copy(WirelessPower rhs) {
    //Create a new customer root to hold for the copy of tree
    //But first check if it's empty.
    if(rhs.m_root == null) {
        return null;
    }
    //Copying the nodes recursively.
    Customer nRoot = copyOfTree(rhs.m_root);
    return nRoot;
}

public String dumpTree() {
    String result = "";
    result = dump(m_root, result);
    return result;
}

public String dump(Customer aCustomer, String result) {
    if (aCustomer == null) {
        return result;
    }
    //System.out.print("Customer: "+aCustomer.getID()+" result: "+result);
    result += "(";
    result = dump(aCustomer.m_left, result);// first visit the left child
    result += aCustomer.m_id + ":" + aCustomer.m_height;// second visit the node itself
    result = dump(aCustomer.m_right, result);// third visit the right child
    result += ")";
    return result;
}

// ***********************************************************************************************
// Used for testing - provided for you
// ***********************************************************************************************
public Customer getRoot() {
    return m_root;
}

public String listCustomers() {
    String result = "";
    result = list(m_root, result);
    return result.trim();
}

private String list(Customer aCustomer, String result) {
    if (aCustomer == null) {
        return result;
    }
    //System.out.println("Customer: " + aCustomer.getID() + " result: " + result);
    result = list(aCustomer.m_left, result);// first visit the left child
    // second visit the node itself
    result += aCustomer.m_id + ":" + aCustomer.getLatitude() + ":" + aCustomer.getLongitude() + "\n";
    result = list(aCustomer.m_right, result);// third visit the right child
    return result;
}

private Customer m_root;       //the root of the BST
private TREETYPE m_type;        // the type of tree, BST, AVL or SPLAY

// ***************************************************
// Any private helper functions must be delared here!
// ***************************************************

//Function to check if tree is empty.
private boolean isEmpty() {
    return m_root == null;
}

//Helper function to recursively copy a tree structure
private Customer copyOfTree(Customer node){
    //Base case
        if(node == null) {
            return null;
        }
    //Creating a new customer with the same properties..
    Customer newCustomer = new Customer(node.getID(),node.getLatitude(),node.getLongitude());

    //Recursively copy the left and right child
    newCustomer.setLeft(copyOfTree(node.getLeft()));
    newCustomer.setRight(copyOfTree(node.getRight()));
    //Also copying the height
    newCustomer.setHeight((node.getHeight()));

    return newCustomer;
}


//Calculate balance factor.
private int getBalance(Customer node) {
    // Base case
    if (node == null) {
        return 0;
    }

    int leftHeight = getHeight(node.getLeft());
    int rightHeight = getHeight(node.getRight());

    return leftHeight - rightHeight; 
}


//AVL Balance 
private Customer balance(ArrayList<Customer> node) {
    // Traverse from bottom (the most recently inserted node) to the root
    for (int i = node.size() - 1; i >= 0; i--) {
        Customer currNode = node.get(i);
        // Update the height of the current node
        updateHeight(currNode);

        // Balance the current node and set it to its parent
        Customer balancedNode = performRotation(currNode);
        
        // Update the current node's reference in the parent
        if (i > 0) {
            Customer parentNode = node.get(i - 1);
            if (parentNode.getLeft() == currNode) {
                parentNode.setLeft(balancedNode);
            } else {
                parentNode.setRight(balancedNode);
            }
        } else {
            return balancedNode; // Return the new root if we're at the top
        }
    }
    return node.get(0); // Return the root node at the end
}

private Customer performRotation(Customer node) {
    // Left Left Case
    if (getBalance(node) > 1 && getBalance(node.getLeft()) >= 0) {
        return rightRotate(node);
    }
    // Left Right Case
    if (getBalance(node) > 1 && getBalance(node.getLeft()) < 0) {
        node.setLeft(leftRotate(node.getLeft()));
        return rightRotate(node);
    }
    // Right Right Case
    if (getBalance(node) < -1 && getBalance(node.getRight()) <= 0) {
        return leftRotate(node);
    }
    // Right Left Case
    if (getBalance(node) < -1 && getBalance(node.getRight()) > 0) {
        node.setRight(rightRotate(node.getRight()));
        return leftRotate(node);
    }
    return node; // Return node if no rotations were needed
}

//Perform right rotation for AVL tree.
private Customer rightRotate (Customer y) {
    //Making x the new root of the subtree.
    Customer x = y.getLeft();
    //Storing the right child of x.
    Customer temp = x.getRight();
    
    //Rotate to ->
    //y becomes the right child of x
    x.setRight(y);
    //temp(the right child of x) becomes the left child
    //Of y
    y.setLeft(temp);
    
    //Now we update the heights.
    updateHeight(y);
    updateHeight(x);
    
    //New root
    return x;
}

//Perform left rotation for AVL tree.
private Customer leftRotate(Customer y) {
    //Making x the new root of the subtree.
    Customer x = y.getRight();
    //Storing the left child of x
    Customer temp = x.getLeft();
    
    //Rotate to <- 
    //y become the left child of x.
    x.setLeft(y);
    //temp(the left child of x) becomes the right child
    //Of Y
    y.setRight(temp);
    
    //Update height
    updateHeight(y);
    updateHeight(x);
    
    return x;
}

//Rotate function for splay to the left.
private Customer leftRotateSplay(Customer x) {
    
    // No rotation possible for these two cases 
    if(x == null) {
        return x;
    }
    
    if(x.getRight() == null) {
        return x;
    }
    //Y is the new root after totation
    Customer y = x.getRight();
    //Move the left child of y to be the right child of x 
    x.setRight(y.getLeft());
    //Rotatiing here
    y.setLeft(x);

    updateHeight(x);
    updateHeight(y);
    return y;
}

//Rotate function for splay to the right
private Customer rightRotateSplay (Customer x ) {
    
    // No rotation possible for these two cases 
    if(x == null) {
        return x;
    }
    
    if(x.getLeft() == null) {
        return x;
    }

    //Y is the new root after rotation
    Customer y = x.getLeft();
    //Move the right child of y to be the left child of x
    x.setLeft(y.getRight());
    //Rotating here
    y.setRight(x);

    updateHeight(x);
    updateHeight(y);
    return y; 
}

//Updates the height of tree.
private void updateHeight(Customer node) {
    if (node != null) {
    // Calculate the height of left and right children
    int leftHeight = getHeight(node.getLeft());
    int rightHeight = getHeight(node.getRight());

    // Update the height of the current node
    node.setHeight(1 + Math.max(leftHeight, rightHeight));
}
}


// Get the height of a node
private int getHeight(Customer node) {
    if (node == null) {
        return -1;  // 
         } else {
        return node.getHeight();
        }
    }

//Deletes nodes from a tree recursively.
private Customer deleteRecursively(Customer node, int id, ArrayList<Customer> pathNodes) {
    if (node == null) {
        return null; // Node not found, return null
    }

    // Add the current node to the path
    pathNodes.add(node);

    if (id < node.getID()) {
        node.setLeft(deleteRecursively(node.getLeft(), id, pathNodes));
    } else if (id > node.getID()) {
        node.setRight(deleteRecursively(node.getRight(), id, pathNodes));
    } else {
        // Node to be deleted found
        if (node.getLeft() == null) {
            return node.getRight(); // No left child, replace with right child
        } else if (node.getRight() == null) {
            return node.getLeft(); // No right child, replace with left child
        }

        // Node with two children: Get the inorder successor
        Customer temp = minValueNode(node.getRight());

        // Copy the inorder successor's data to this node
        node.setID(temp.getID());
        node.setLatitude(temp.getLatitude());
        node.setLongitude(temp.getLongitude());

        // Delete the inorder successor
        node.setRight(deleteRecursively(node.getRight(), temp.getID(), pathNodes));
    }

    // After deletion, update the height and rebalance
    updateHeight(node);
    return balance(pathNodes); // Rebalance after deletion
}



private Customer minValueNode(Customer node) {
    Customer current = node;
    while (current.getLeft() != null) {
        current = current.getLeft();
    }
    return current;
}



//Help find the mininum 
private Customer findMin(Customer node) {
    //Go to the left most child in tree (Min)
    while(node.getLeft() != null & node.getLeft() != null) {
        node = node.getLeft();
    }
    return node;
}



public void BstToAVL() {
    // Creating an ArrayList to hold the nodes in sorted order
    ArrayList<Customer> nodeList = new ArrayList<>();
    
    // Filling the ArrayList with nodes in sorted order
    traverseInOrder(m_root, nodeList);
    
    // Converting the ArrayList to an AVL tree
    m_root = arrayToAVL(nodeList, 0, nodeList.size() - 1);
}

// Recursively build the AVL tree subtrees
private Customer arrayToAVL(ArrayList<Customer> nodeList, int start, int end) {
    // No elements left in our tree
    if (start > end) {
        return null;
    }
    // Find the middle of the ArrayList. 
    int mid = (start + end) / 2; 
    // Create a root node
    Customer node = nodeList.get(mid); 

    // Create the left subtree 
    node.setLeft(arrayToAVL(nodeList, start, mid - 1));
    // Create the right subtree
    node.setRight(arrayToAVL(nodeList, mid + 1, end));
    
    return node;
}

// Traverse tree in order (Left subtree then root, then right subtree)
// While storing the values into our ArrayList.
private void traverseInOrder(Customer node, ArrayList<Customer> nodeList) {
    // If node is null, no nodes left
    if (node == null) {
        return;
    }
    // Traverse left of subtree first 
    traverseInOrder(node.getLeft(), nodeList);
    // Add the current node to our ArrayList
    nodeList.add(node); 
    // Traverse right of subtree afterwards
    traverseInOrder(node.getRight(), nodeList);
}



   //Helper function to insert a BST Tree.
   private Customer insertBST(Customer node, Customer aCustomer, ArrayList<Customer> tempNodes) {
    //Base case 
    if (node == null) {
        return new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude());
    }

    //If key already in the tree return the node.
    //No Duplicates.
    if(node.getID() == aCustomer.getID()) {
        return node;
    }

    //Adding current node to the list
    tempNodes.add(node);

    //Down the tree..
    if(aCustomer.getID() < node.getID()) {
        node.setLeft(insertBST(node.getLeft(), aCustomer, tempNodes));
    } else {
        node.setRight(insertBST(node.getRight(), aCustomer, tempNodes));
    }

    //Update the height of the ancestor node
    updateHeight(node);

    return node;

}


//AVL Insertion
private Customer insertAVL(Customer node, Customer aCustomer, ArrayList<Customer> tempNodes) {
    // If the tree is empty, create a new node and return it
    if (node == null) {
        return new Customer(aCustomer.getID(), aCustomer.getLatitude(), aCustomer.getLongitude());
    }

    // If the key already exists, return the node (no duplicates)
    if (node.getID() == aCustomer.getID()) {
        return node; // Early return to prevent infinite recursion on duplicates
    }

    // Add the current node to the list
    tempNodes.add(node);

    // Traverse the tree and insert the new customer
    if (aCustomer.getID() < node.getID()) {
        System.out.println("Going left: " + node.getID());
        node.setLeft(insertAVL(node.getLeft(), aCustomer, tempNodes));
    } else {
        System.out.println("Going right: " + node.getID());
        node.setRight(insertAVL(node.getRight(), aCustomer, tempNodes));
    }

    // Update the height of the ancestor node
    updateHeight(node);

    // Balance the node and return the potentially new root of this subtree
    return balance(tempNodes);
}






private Customer splay(Customer node, Customer aCustomer) {
    // Base case: if node is null or key is found
    if (node == null || node.getID() == aCustomer.getID()) {
        return node;
    }

    // Our ID is in the left subtree
    if (aCustomer.getID() < node.getID()) {
        // If left child is null return node (key not found)
        if (node.getLeft() == null) {
            return node;
        }

        // Zig-Zig (Left Left)
        if (aCustomer.getID() < node.getLeft().getID()) {
            // splay the left left grandchild
            node.getLeft().setLeft(splay(node.getLeft().getLeft(), aCustomer));
            // perform first right rotation
            node = rightRotateSplay(node);
        }
        // Zig-Zag (Left Right)
        else if (aCustomer.getID() > node.getLeft().getID()) {
            // splay the left right grandchild
            node.getLeft().setRight(splay(node.getLeft().getRight(), aCustomer));
            // perform left rotation on left child
            if (node.getLeft().getRight() != null) {
                node.setLeft(leftRotateSplay(node.getLeft()));
            }
        }

        //second right rotation if needed
        if (node.getLeft() == null) {
            // return the current node if the left child is null
            return node; 
        } else {
            return rightRotateSplay(node);
        }
    } else {
    // Our id in the right subtree
        // If right child is null return node (key not found)
        if (node.getRight() == null) {
            return node;
        }
        // Zag-Zag (Right Right)
        if (aCustomer.getID() > node.getRight().getID()) {
            //splay the right-right grandchild
            node.getRight().setRight(splay(node.getRight().getRight(), aCustomer));
            //first left rotation
            node = leftRotateSplay(node);
        } 
        // Zag-Zig (Right Left)
        else if (aCustomer.getID() < node.getRight().getID()) {
            // splay the right-left grandchild
            node.getRight().setLeft(splay(node.getRight().getLeft(), aCustomer));
            //right rotation on right child
            if (node.getRight().getLeft() != null) {
                node.setRight(rightRotateSplay(node.getRight()));
            }
        }

        if (node.getRight() == null) {
            return node; 
        } else {
            return leftRotateSplay(node); 
        }
    }
}




class Customer {
    int DEFAULT_HEIGHT = 0;
    int DEFAULT_ID = 0;

    Customer(int id, double lat, double longitude){
        m_id = id; m_latitude = lat; m_longitude = longitude;
        m_left = null; m_right = null; m_height = DEFAULT_HEIGHT;
    }
    //used for testing that ids are put in trees correctly
    Customer(int id){
        m_id = id; m_latitude = 0; m_longitude = 0;
        m_left = null; m_right = null; m_height = DEFAULT_HEIGHT;

    }
    int getHeight() {return m_height;}
    Customer getLeft() {return m_left;}
    Customer getRight() {return m_right;}
    int getID() {return m_id;}
    double getLatitude() {return m_latitude;}
    double getLongitude() {return m_longitude;}
    void setID(int id){m_id=id;}
    void setLatitude(double lat) {m_latitude=lat;}
    void setLongitude(double longitude) {m_longitude=longitude;}
    void setHeight(int height){m_height=height;}
    void setLeft(Customer left){m_left=left;}
    void setRight(Customer right){m_right=right;}
    String getLatStr() {
        String text = "";
        int latSeconds = (int)(Math.abs(m_latitude * 3600));
        int latDegrees = latSeconds / 3600;
        latSeconds = latSeconds % 3600;
        int latMinutes = latSeconds / 60;
        latSeconds %= 60;
        char latDirection = (m_latitude >= 0) ? 'N' : 'S';
        text = Integer.toString(latDegrees) + "\u00B0 " + Integer.toString(latMinutes) + "' " + 
                Integer.toString(latSeconds) + "\" " + latDirection;
        return text;
    }
    String getLongStr() {
        String text = "";
        int longSeconds = (int)(Math.abs(m_longitude * 3600));
        int longDegrees = longSeconds / 3600;
        longSeconds = longSeconds % 3600;
        int longMinutes = longSeconds / 60;
        longSeconds %= 60;
        char longDirection = (m_longitude >= 0) ? 'E' : 'W';
        text = Integer.toString(longDegrees) + "\u00B0 " + Integer.toString(longMinutes) + "' " + 
                Integer.toString(longSeconds) + "\" " + longDirection;
        return text;
    }

    //private data members
    private int m_id;
    private double m_latitude;
    private double m_longitude;
    private Customer m_left;    //the pointer to the left child in the BST
    private Customer m_right;   //the pointer to the right child in the BST
    private int m_height;        //the height of node in the BST
    
} // end of class Customer
} //end of class WirelessPower 

Im running into a problem with this code when running these test 

import static org.junit.jupiter.api.Assertions.*;

import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

class WirelessPowerTestAVL {
	WirelessPower s1,s2,s3;
	WirelessPower.Customer d0,d1,d2,d3,d4,d5,d6,d7,d8,d9;
	
	@BeforeEach
	void setUp() throws Exception {
		s2 = new WirelessPower(TREETYPE.BST);
		s3 = new WirelessPower(TREETYPE.SPLAY);
		s1 = new WirelessPower(TREETYPE.AVL);
		d0 = s1.new Customer(10000); // min id
		d1 = s1.new Customer(53002,51.5078,-0.0878);//London Bridge (North & West)
		d2 = s1.new Customer(20201, 39.2554, -76.7107); //Catonsville campus (North & West)
		d3 = s1.new Customer(60496, 48.8584, 2.2945); //Eiffel Tower (North & East)
		d4 = s1.new Customer(19289,43.6150,-116.2023);//Boise, ID (North & West)
		d5 = s1.new Customer(27904, 55.7558, 37.6173);//Catherine Palace Moscow Russia (North & East)
		d6 = s1.new Customer(93209, -33.8568, 151.2153);//Sydney Opera House (South & East)
		d7 = s1.new Customer(19224, 40.4319,116.5704);//Great Wall of China (North & East)
		d8 = s1.new Customer(19372, 27.1751, 78.0421);//Taj Mahal (North & East)
		d9 = s1.new Customer(26241, -13.1632,-72.5453);//Machu Picchu (South & West)
	}

	@AfterEach
	void tearDown() throws Exception {
		s3 = s2 = s1 = null;
	}

	@Test
	void testWirelessPowerConstructor() {
		assertNull(s1.getRoot());
		assertTrue(s2.getRoot() == null);
		assertFalse(s3.getRoot() != null);
		assertEquals(TREETYPE.AVL,s1.getType());
		assertEquals(TREETYPE.BST,s2.getType());
		assertEquals(TREETYPE.SPLAY,s3.getType());
	}

	@Test
	void testInsertEasyAVL() {
		s1.insert(d1);
		//this Customer is the root of the tree
		assertEquals(53002,s1.getRoot().getID());
		assertEquals(51.5078, s1.getRoot().getLatitude());
		assertEquals(-0.0878, s1.getRoot().getLongitude());

		//insert to the left of the root
		s1.insert(d2);
		assertEquals(20201,s1.getRoot().getLeft().getID());
		assertEquals(39.2554, s1.getRoot().getLeft().getLatitude());
		assertEquals(-76.7107, s1.getRoot().getLeft().getLongitude());

		//insert to the right of the root
		s1.insert(d3);
		assertEquals(60496,s1.getRoot().getRight().getID());
		assertEquals(48.8584, s1.getRoot().getRight().getLatitude());
		assertEquals(2.2945, s1.getRoot().getRight().getLongitude());
		//check the heights
		assertEquals("((20201:0)53002:1(60496:0))",s1.dumpTree());
	}

	@Test
	void testInsertAVLNoRebalance() {
		s1.insert(d1); //root
		s1.insert(d2); //left of root
		s1.insert(d3); //right of root
		s1.insert(d4); //left of left of root
		s1.insert(d5); //right of left of root
		s1.insert(d6); //right of right of root
		s1.insert(d7);//left of left of left of root
		s1.insert(d8); //right of left of left of root
		s1.insert(d9); //left of right of left of root
		assertEquals(53002,s1.getRoot().getID());
		assertEquals(60496,s1.getRoot().getRight().getID());
		assertEquals(20201,s1.getRoot().getLeft().getID());
		assertEquals(19289,s1.getRoot().getLeft().getLeft().getID());
		assertEquals(27904,s1.getRoot().getLeft().getRight().getID());
		assertEquals(93209,s1.getRoot().getRight().getRight().getID());
		assertEquals(19224,s1.getRoot().getLeft().getLeft().getLeft().getID());
		assertEquals(19372,s1.getRoot().getLeft().getLeft().getRight().getID());
		assertEquals(26241,s1.getRoot().getLeft().getRight().getLeft().getID());
		assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree());		
	}
	
	@Test
	void testInsertRebalanceEasyAVL() {
		s1.insert(d1); //root
		s1.insert(d2); //left of root
		s1.insert(d4); //left of left of root
		//requires a rebalance
		assertEquals(20201,s1.getRoot().getID());
		assertEquals(53002,s1.getRoot().getRight().getID());
		assertEquals(19289,s1.getRoot().getLeft().getID());
		//check the heights
		assertEquals("((19289:0)20201:1(53002:0))",s1.dumpTree());

	}
	
	@Test
	void testInsertDeepCopyOfParameterAVL() {
		s1.insert(d1);
		s1.insert(d2);
		assertEquals("20201:39.2554:-76.7107\n53002:51.5078:-0.0878",s1.listCustomers());
		d1.setID(93300);
		s1.insert(d1);
		assertEquals("20201:39.2554:-76.7107\n53002:51.5078:-0.0878\n93300:51.5078:-0.0878",s1.listCustomers());
		//check the heights
		assertEquals("((20201:0)53002:1(93300:0))",s1.dumpTree());

	}

	@Test
	void testInsertRebalanceAVL() {
		s1.insert(d1); //root
		s1.insert(d2); //left of root
		s1.insert(d3); //right of root
		s1.insert(d4); //left of left of root		
		s1.insert(d7);//left of left of left of root
		
		assertEquals(53002,s1.getRoot().getID());
		assertEquals(60496,s1.getRoot().getRight().getID());
		assertEquals(19289,s1.getRoot().getLeft().getID());
		assertEquals(19224,s1.getRoot().getLeft().getLeft().getID());
		assertEquals(20201,s1.getRoot().getLeft().getRight().getID());
		System.out.println(s1.dumpTree());
	}
	
	@Test
	void testInsertDuplicateAVL() {
		s1.insert(d1);
		s1.insert(d2);
		s1.insert(d3);
		assertEquals("20201:39.2554:-76.7107\n53002:51.5078:-0.0878\n60496:48.8584:2.2945",s1.listCustomers());
		s1.insert(s1.new Customer(60496));
		//No duplicate IDs
		assertEquals("20201:39.2554:-76.7107\n53002:51.5078:-0.0878\n60496:48.8584:2.2945",s1.listCustomers());
	}

	@Test
	void testInsertErrorAVL() {
		WirelessPower.Customer d10 = s1.new Customer(500,48.8584,2.2945);
		s1.insert(d10);
		//ID is less than minimum
		assertNull(s1.getRoot());
	}

	@Test
	void testClearAVL() {
		//create a tree
		s1.insert(d1);
		s1.insert(d2);
		s1.insert(d3);
		s1.clear();
		assertNull(s1.getRoot());
	}


	@Test
	void testRemoveEasyAVL() {
		//create a simple tree
		s1.insert(d1);
		s1.insert(d2);
		s1.insert(d3);
		//remove the node to the right of the root
		s1.remove(60496); //this is d3
		assertNull(s1.getRoot().getRight());
		//check the heights
		assertEquals("((20201:0)53002:1)",s1.dumpTree());

	}
	
	@Test
	void testRemoveNoRebalanceAVL() {
		//create a simple tree
		s1.insert(d1); //root
		s1.insert(d2); //left of root
		s1.insert(d3); //right of root
		//insert d6 (goes to right of right of root)
		s1.insert(d6);
		
		//delete 60496 which is right of root with a right child
		s1.remove(60496);
		//93209 (d6) should now be right of root
		assertEquals(93209, s1.getRoot().getRight().getID());
	}

	@Test
	void testRemoveRebalanceEasyAVL() {
		s1.insert(d1); //root
		s1.insert(d2); //left of root
		s1.insert(d3); //right of root
		s1.insert(d4); //left of left of root
		s1.insert(d5); //right of left of root
		s1.insert(d6); //right of right of root
		s1.insert(d7);//left of left of left of root
		
		//delete 27904 which is right of left of root and requires a rebalance
		s1.remove(27904);
		assertEquals(53002,s1.getRoot().getID());
		assertEquals(60496,s1.getRoot().getRight().getID());
		assertEquals(19289,s1.getRoot().getLeft().getID());
		assertEquals(19224,s1.getRoot().getLeft().getLeft().getID());
		assertEquals(20201,s1.getRoot().getLeft().getRight().getID());
		//check the heights
		assertEquals("(((19224:0)19289:1(20201:0))53002:2(60496:1(93209:0)))",s1.dumpTree());
	}

	@Test
	void testHeightChangesAVL() {
		s1.insert(d1); //root
		s1.insert(d2); //left of root
		s1.insert(d3); //right of root
		assertEquals(1,s1.getRoot().getHeight());
		s1.insert(d4); //left of left of root
		s1.insert(d5); //right of left of root
		s1.insert(d6); //right of right of root
		assertEquals(2,s1.getRoot().getHeight());
		s1.insert(d7);//left of left of left of root
		s1.insert(d8); //right of left of left of root
		s1.insert(d9); //left of right of left of root
		assertEquals(3,s1.getRoot().getHeight());
		//check the heights
		assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree());

	}

	@Test
	void testRemoveNoRebalAVL() {
		s1.insert(d1); //root
		s1.insert(d2); //left of root
		s1.insert(d3); //right of root
		s1.insert(d4); //left of left of root
		s1.insert(d5); //right of left of root
		s1.insert(d6); //right of right of root
		s1.insert(d7);//left of left of left of root
		s1.insert(d8); //right of left of left of root
		s1.insert(d9); //left of right of left of root
		String result = s1.listCustomers();
		assertEquals("19224:40.4319:116.5704\n19289:43.615:-116.2023\n19372:27.1751:78.0421\n20201:39.2554:-76.7107\n26241:-13.1632:-72.5453\n27904:55.7558:37.6173\n53002:51.5078:-0.0878\n60496:48.8584:2.2945\n93209:-33.8568:151.2153",result);
		s1.remove(19372);
		result = s1.listCustomers();
		assertEquals("19224:40.4319:116.5704\n19289:43.615:-116.2023\n20201:39.2554:-76.7107\n26241:-13.1632:-72.5453\n27904:55.7558:37.6173\n53002:51.5078:-0.0878\n60496:48.8584:2.2945\n93209:-33.8568:151.2153",result);
		//check the heights
		assertEquals("((((19224:0)19289:1)20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree());

	}

	@Test
	void testRemoveReBalEasyAVL() {
		s1.insert(d1); //root
		s1.insert(d2); //left of root
		s1.insert(d3); //right of root
		s1.insert(d4); //left of left of root
		s1.insert(d5); //right of left of root
		s1.insert(d6); //right of right of root
		s1.insert(d7);//left of left of left of root
		
		System.out.println(s1.dumpTree());
		String result = s1.listCustomers();
		assertEquals("19224:40.4319:116.5704\n19289:43.615:-116.2023\n20201:39.2554:-76.7107\n27904:55.7558:37.6173\n53002:51.5078:-0.0878\n60496:48.8584:2.2945\n93209:-33.8568:151.2153",result);
		s1.remove(27904);
		result = s1.listCustomers();
		assertEquals("19224:40.4319:116.5704\n19289:43.615:-116.2023\n20201:39.2554:-76.7107\n53002:51.5078:-0.0878\n60496:48.8584:2.2945\n93209:-33.8568:151.2153",result);
		assertEquals("(((19224:0)19289:1(20201:0))53002:2(60496:1(93209:0)))",s1.dumpTree());
	}
		

	@Test
	void testCopyConstructorEasyAVL() {
		s1.insert(d1);
		s1.insert(d2);
		s1.insert(d3);
		assertEquals("((20201:0)53002:1(60496:0))",s1.dumpTree());
		WirelessPower s4 = new WirelessPower(s1);

		// this Customer is the root of the tree
		assertEquals(53002, s4.getRoot().getID());
		assertEquals(51.5078, s4.getRoot().getLatitude());
		assertEquals(-0.0878, s4.getRoot().getLongitude());

		// left of the root
		assertEquals(20201, s4.getRoot().getLeft().getID());
		assertEquals(39.2554, s4.getRoot().getLeft().getLatitude());
		assertEquals(-76.7107, s4.getRoot().getLeft().getLongitude());

		// right of the root
		assertEquals(60496, s4.getRoot().getRight().getID());
		assertEquals(48.8584, s4.getRoot().getRight().getLatitude());
		assertEquals(2.2945, s4.getRoot().getRight().getLongitude());
		assertEquals("((20201:0)53002:1(60496:0))",s1.dumpTree());
		assertEquals("((20201:0)53002:1(60496:0))", s4.dumpTree());
	}

	@Test
	void testCopyConstructorAVL() {
		s1.insert(d1); //root
		s1.insert(d2); //left of root
		s1.insert(d3); //right of root
		s1.insert(d4); //left of left of root
		s1.insert(d5); //right of left of root
		s1.insert(d6); //right of right of root
		s1.insert(d7);//left of left of left of root
		s1.insert(d8); //right of left of left of root
		s1.insert(d9); //left of right of left of root
		WirelessPower s4 = new WirelessPower(s1);
		assertEquals(53002,s4.getRoot().getID());
		assertEquals(60496,s4.getRoot().getRight().getID());
		assertEquals(20201,s4.getRoot().getLeft().getID());
		assertEquals(19289,s4.getRoot().getLeft().getLeft().getID());
		assertEquals(27904,s4.getRoot().getLeft().getRight().getID());
		assertEquals(93209,s4.getRoot().getRight().getRight().getID());
		assertEquals(19224,s4.getRoot().getLeft().getLeft().getLeft().getID());
		assertEquals(19372,s4.getRoot().getLeft().getLeft().getRight().getID());
		assertEquals(26241,s4.getRoot().getLeft().getRight().getLeft().getID());	
	}

	@Test
	void testSetTypeAVLtoBST() {
		s1.insert(d1); //root
		s1.insert(d2); //left of root
		s1.insert(d3); //right of root
		s1.insert(d4); //left of left of root
		s1.insert(d5); //right of left of root
		s1.insert(d6); //right of right of root
		s1.insert(d7);//left of left of left of root
		s1.insert(d8); //right of left of left of root
		s1.insert(d9); //left of right of left of root
		assertEquals(53002,s1.getRoot().getID());
		assertEquals(60496,s1.getRoot().getRight().getID());
		assertEquals(20201,s1.getRoot().getLeft().getID());
		assertEquals(19289,s1.getRoot().getLeft().getLeft().getID());
		assertEquals(27904,s1.getRoot().getLeft().getRight().getID());
		assertEquals(93209,s1.getRoot().getRight().getRight().getID());
		assertEquals(19224,s1.getRoot().getLeft().getLeft().getLeft().getID());
		assertEquals(19372,s1.getRoot().getLeft().getLeft().getRight().getID());
		assertEquals(26241,s1.getRoot().getLeft().getRight().getLeft().getID());
		assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree());
		//convert AVL tree to BST tree
		s1.setType(TREETYPE.BST);
		//no change
		assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree());
		assertEquals(TREETYPE.BST,s1.getType());
		
	}

	@Test
	void testSetTypeAVLtoSplay() {
		s1.insert(d1); //root
		s1.insert(d2); //left of root
		s1.insert(d3); //right of root
		s1.insert(d4); //left of left of root
		s1.insert(d5); //right of left of root
		s1.insert(d6); //right of right of root
		s1.insert(d7);//left of left of left of root
		s1.insert(d8); //right of left of left of root
		s1.insert(d9); //left of right of left of root
		assertEquals(53002,s1.getRoot().getID());
		assertEquals(60496,s1.getRoot().getRight().getID());
		assertEquals(20201,s1.getRoot().getLeft().getID());
		assertEquals(19289,s1.getRoot().getLeft().getLeft().getID());
		assertEquals(27904,s1.getRoot().getLeft().getRight().getID());
		assertEquals(93209,s1.getRoot().getRight().getRight().getID());
		assertEquals(19224,s1.getRoot().getLeft().getLeft().getLeft().getID());
		assertEquals(19372,s1.getRoot().getLeft().getLeft().getRight().getID());
		assertEquals(26241,s1.getRoot().getLeft().getRight().getLeft().getID());
		assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree());
		//convert AVL tree to Splay tree
		s1.setType(TREETYPE.SPLAY);
		//no change
		assertEquals(TREETYPE.SPLAY,s1.getType());
		assertEquals("((((19224:0)19289:1(19372:0))20201:2((26241:0)27904:1))53002:3(60496:1(93209:0)))",s1.dumpTree());
		
	}


} 

I'm getting stack overflow on some of them for example 
void testInsertAVLNoRebalance() { is one of them how would i go about fixing this i still want to use arrayList for my implementation of everything since it seems to be the most efficent no? I also cannot modify anything in the test cases or inside of the custoemr class and I cant import any other java utils