Solution: Two Separate Checks

The tree has to pass two checks at every node: the ordering bounds and the balance factor. The straightforward thing is to write each check on its own.

Ordering is the validate-BST recursion, carrying a lower and an upper bound down the tree:

private static <T extends Comparable<T>> boolean isOrdered(Node<T> node, T min, T max) {
  if (node == null) {
    return true;
  }
  if (min != null && node.value.compareTo(min) <= 0) {
    return false;
  }
  if (max != null && node.value.compareTo(max) >= 0) {
    return false;
  }
  return isOrdered(node.left, min, node.value)
      && isOrdered(node.right, node.value, max);
}

At every node, the balance check tests whether the two subtree heights differ by more than one:

private static <T> boolean isBalanced(Node<T> node) {
  if (node == null) {
    return true;
  }
  int bf = height(node.left) - height(node.right);
  if (Math.abs(bf) > 1) {
    return false;
  }
  return isBalanced(node.left) && isBalanced(node.right);
}

private static <T> int height(Node<T> node) {
  if (node == null) {
    return -1;
  }
  return 1 + Math.max(height(node.left), height(node.right));
}

The tree is a valid AVL tree only when both checks pass:

public static <T extends Comparable<T>> boolean isValidAvl(Node<T> root) {
  return isOrdered(root, null, null) && isBalanced(root);
}

This is correct. The ordering check visits each node once, so it is $O (n)$ . The balance check costs more. isBalanced calls height on both children of every node, and height visits every node in the subtree below the node it is given. So each node is visited again inside the height computation of every ancestor above it.

When the tree is valid, every node gets checked, so each node is visited about as many times as its depth. A valid AVL tree is about $lo g n$ tall, so no node is deeper than about $lo g n$ , and the balance check is $O (n lo g n)$ .

The next solution computes each height once.