public class AVLextends Comparablesuper T>> { // DO NOT ADD OR MODIFY INSTANCE VARIABLES.  private AVLNode root; private int size; 

/**  * Returns the data in the deepest node. If there are more than one node  * with the same deepest depth, return the right most node with the  * deepest depth.  *  * Must run in O(log n) for all cases  *  * Example  * Tree:  * 2  * / \  * 0 3  * \  * 1  * Max Deepest Node:  * 1 because it is the deepest node  *  * Example  * Tree:  * 2  * / \  * 0 4  * \ /  * 1 3  * Max Deepest Node:  * 3 because it is the maximum deepest node (1 has the same depth but 3 > 1)  *  * @return the data in the maximum deepest node or null if the tree is empty  */ public T maxDeepestNode() { } /**  * Returns the data of the deepest common ancestor between two nodes with  * the given data. The deepest common ancestor is the lowest node (i.e.  * deepest) node that has both data1 and data2 as descendants.  * If the data are the same, the deepest common ancestor is simply the node  * that contains the data. You may not assume data1 < data2.  * (think carefully: should you use value equality or reference equality?).  *  * Must run in O(log n) for all cases  *  * Example  * Tree:  * 2  * / \  * 0 3  * \  * 1  * deepestCommonAncestor(3, 1): 2  *  * Example  * Tree:  * 3  * / \  * 1 4  * / \  * 0 2  * deepestCommonAncestor(0, 2): 1  *  * @param data1 the first data  * @param data2 the second data  * @throws java.lang.IllegalArgumentException if one or more of the data  * are null  * @throws java.util.NoSuchElementException if one or more of the data are  * not in the tree  * @return the data of the deepest common ancestor  */ public T deepestCommonAncestor(T data1, T data2) { }

}

public class AVLNodeextends Comparablesuper T>> { private T data; private AVLNode left; private AVLNode right; private int height; private int balanceFactor; /**  * Create an AVL node with the specified data.  *  * @param data the data to be stored in this node  */  public AVLNode(T data) { this.data = data; } /**  * Get the data in this node.  *  * @return data in this node  */  public T getData() { return data; } /**  * Set the data in this node.  *  * @param data data to store in this node  */  public void setData(T data) { this.data = data; } /**  * Get the node to the left of this node.  *  * @return node to the left of this node.  */  public AVLNode getLeft() { return left; } /**  * Set the node to the left of this node.  *  * @param left node to the left of this node  */  public void setLeft(AVLNode left) { this.left = left; } /**  * Get the node to the right of this node.  *  * @return node to the right of this node.  */  public AVLNode getRight() { return right; } /**  * Set the node to the right of this node.  *  * @param right node to the right of this node  */  public void setRight(AVLNode right) { this.right = right; } /**  * Get the height of this node.  *  * @return height of this node  */  public int getHeight() { return height; } /**  * Set the height of this node.  *  * @param height height of this node  */  public void setHeight(int height) { this.height = height; } /**  * Get the balance factor of this node.  *  * @return balance factor of this node.  */  public int getBalanceFactor() { return balanceFactor; } /**  * Set the balance factor of this node.  *  * @param balanceFactor balance factor of this node  */  public void setBalanceFactor(int balanceFactor) { this.balanceFactor = balanceFactor; } 

}