find max deepest node in AVL tree.

 public class AVLextends Comparablesuper T>> { // DO NOT ADD OR MODIFY INSTANCE VARIABLES.  private AVLNode root; private int size; /**  * A no-argument constructor that should initialize an empty AVL.  *  * Since instance variables are initialized to their default values, there  * is no need to do anything for this constructor.  */  public AVL() { // DO NOT IMPLEMENT THIS CONSTRUCTOR!  }

/**  * 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() { if (root == null) { return null; } // ...code here }

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; } /**  * DO NOT USE EXCEPT FOR DEBUGGING PURPOSES  */  @Override public String toString() { return String.format("Node containing %s (height %d, bf %d)", data.toString(), height, balanceFactor); } }