Solution: One Post-Order Pass

The two separate checks compute each node’s height again for every ancestor. The balance check needs each node’s height, and a node’s height is one more than the taller of its children’s heights. If the recursion returns a subtree’s height as it unwinds, every parent gets its children’s heights from its own recursive calls, with no second traversal. So combine both checks into one post-order recursion that returns the height of the subtree it just validated.

We still need a way to report failure. Let the recursion return a sentinel, a value no real height can ever be, as soon as any check fails, and have each caller return that sentinel immediately without running its remaining checks.

private static final int INVALID = Integer.MIN_VALUE;

public static <T extends Comparable<T>> boolean isValidAvl(Node<T> root) {
  return check(root, null, null) != INVALID;
}

private static <T extends Comparable<T>> int check(Node<T> node, T min, T max) {
  if (node == null) {
    return -1;  // height of an empty subtree
  }

  // ordering: the node must fall inside the bounds its ancestors set
  if (min != null && node.value.compareTo(min) <= 0) {
    return INVALID;
  }
  if (max != null && node.value.compareTo(max) >= 0) {
    return INVALID;
  }

  int left = check(node.left, min, node.value);
  if (left == INVALID) {
    return INVALID;
  }

  int right = check(node.right, node.value, max);
  if (right == INVALID) {
    return INVALID;
  }

  // balance: the two subtree heights may differ by at most one
  if (Math.abs(left - right) > 1) {
    return INVALID;
  }

  return 1 + Math.max(left, right);  // this subtree's height
}

One call does everything for one node. It checks the ordering bounds first. It recurses left, passing the node’s value as the new upper bound, then recurses right, passing the node’s value as the new lower bound. It checks that the two heights it got back differ by at most one. Then it returns its own height. As soon as any of those fails, it returns INVALID, and each caller returns INVALID immediately.

Real heights are always $- 1$ or greater, so Integer.MIN_VALUE can never be mistaken for one. And by the time we reach Math.abs(left - right), both left and right are real heights, because the call has already returned if either one is INVALID.

Tracing a valid tree

Take this tree first and follow the height each call returns:

        ╭────╮
        │ 30 │
        ╰──┬─╯
   ┌───────┴───────┐
╭──┴─╮          ╭──┴─╮
│ 20 │          │ 50 │
╰────╯          ╰──┬─╯
               ┌───┘
            ╭──┴─╮
            │ 40 │
            ╰────╯

The recursion goes down to the leftmost node before it returns anything. check(20, -inf, 30) finds 20 in range and sees two empty children, each check(null, ...) returning $- 1$ . The heights $- 1$ and $- 1$ differ by $0$ , which is within one, so 20 returns $1 + max (- 1, - 1) = 0$ .

Back at the root, left is $0$ . Now check(50, 30, inf) runs. 50 is in range; its left child check(40, 30, 50) returns $0$ the same way 20 did, and its right child is empty, returning $- 1$ . The heights $0$ and $- 1$ differ by one, which is allowed, so 50 returns $1 + max (0, - 1) = 1$ .

The root now has left $= 0$ and right $= 1$ . They differ by one, so 30 is balanced, and it returns $1 + max (0, 1) = 2$ . That is not INVALID, so isValidAvl returns true.

Tracing a violating tree

Now take the tree from the problem statement that is in order but unbalanced: 30 is the left child of 50, and 20 is the left child of 30. The recursion goes down to 20 before anything returns. 20 is a leaf, so both its children are empty and it returns height $0$ .

call stack

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ check(node=20)  range (-inf, 30)  ┃
        ┃   return 0  (leaf)                ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
        ┌───────────────────────────────────┐
        │ check(node=30)  range (-inf, 50)  │
        │   waiting for check(30.left)      │
        ├───────────────────────────────────┤
        │ check(node=50)  range (-inf, inf) │
        │   waiting for check(50.left)      │
        └───────────────────────────────────┘

tree

        ╭────╮
        │ 50 │
        ╰──┬─╯
       ┌───┘
    ╭──┴─╮
    │ 30 │
    ╰──┬─╯
   ┌───┘
╭──┴─╮
│█20█│
╰────╯

check(30) takes that $0$ as its left height, recurses right into an empty subtree for a right height of $- 1$ , and finds $∣0 - (- 1) ∣ = 1$ , within one. So 30 is balanced and returns its own height, $1$ .

call stack

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ check(node=30)  range (-inf, 50)  ┃
        ┃   return 1  (|0 - (-1)| = 1)      ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
        ┌───────────────────────────────────┐
        │ check(node=50)  range (-inf, inf) │
        │   waiting for check(50.left)      │
        └───────────────────────────────────┘

tree

        ╭────╮
        │ 50 │
        ╰──┬─╯
       ┌───┘
    ╭──┴─╮
    │█30█│
    ╰──┬─╯
   ┌───┘
╭──┴─╮
│ 20 │
╰────╯

check(50) takes that $1$ as its left height and recurses right into an empty subtree, getting $- 1$ . Now the balance check fails: $∣1 - (- 1) ∣ = 2$ , which is more than one. 50 returns INVALID.

call stack

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ check(node=50)  range (-inf, inf)  ┃
        ┃   return INVALID  (|1 - (-1)| = 2) ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

tree

        ╭────╮
        │█50█│
        ╰──┬─╯
       ┌───┘
    ╭──┴─╮
    │ 30 │
    ╰──┬─╯
   ┌───┘
╭──┴─╮
│ 20 │
╰────╯

There is no node above 50, so INVALID goes back to isValidAvl. It compares the result against INVALID and returns false. The recursion does not look at any more nodes.

call stack

        (empty — all calls have returned)

tree

        ╭────╮
        │█50█│
        ╰──┬─╯
       ┌───┘
    ╭──┴─╮
    │ 30 │
    ╰──┬─╯
   ┌───┘
╭──┴─╮
│ 20 │
╰────╯

Cost

Each node is visited once, and beyond its two recursive calls it does a constant amount of work: two comparisons for ordering, one subtraction and one comparison for balance, one max. So the single pass is $O (n)$ time. The recursion goes as deep as the tree, so it uses $O (h)$ space on the call stack, where $h$ is the height of the tree.