package weblab;
import java.lang.Math;
class Solution {

  /**
   * Computes whether the BinaryTree is an AVL tree.
   *
   * @param tree
   *     the BinaryTree to check.
   * @return true iff the BinaryTree is an AVL tree, else false.
   */
  public static boolean isTreeAVL(BinaryTree tree) {
    return isTreeBST(tree, Integer.MIN_VALUE, Integer.MAX_VALUE);
  }


  public static boolean isTreeBST(BinaryTree tree, int min, int max){

    if (tree == null){
      return true;
    }

    if (tree.getKey() <= min || tree.getKey() >= max){
      return false;
    }



    if (tree.hasLeft()){
      if(!isTreeBST(tree.getLeft(), min, tree.getKey())){
        return false;
      }
    }

    if (tree.hasRight()){
      if(!isTreeBST(tree.getRight(), tree.getKey(), max)){
        return false;
        }
    }

    if ((size(tree.getRight())- size(tree.getLeft()) > 1 || (size(tree.getRight())- size(tree.getLeft())) < -1 )){
      return false;
    }

    return true;
  }

  public static int size(BinaryTree tree){
    if (tree == null){
      return 0;
    }
    return 1 + Math.max(size(tree.getRight()), size(tree.getLeft()));
  }


}