Problem: Validating an AVL Tree

An AVL tree has two properties. It is a binary search tree, so its values are in search order, and it is balanced. Checking one property is not enough. A tree can satisfy either one and fail the other.

Use the binary tree node from the tree chapter:

public class Node<T> {
  public T value;
  public Node<T> left;
  public Node<T> right;

  public Node(T value) {
    this.value = value;
  }
}

Write this method:

public static <T extends Comparable<T>> boolean isValidAvl(Node<T> root) {

}

An empty tree is valid. A tree with a duplicate value is not valid.

Treat the tree as untrusted input. You are deciding whether it is a valid AVL tree, so you cannot assume anything about how it was built. You have to compute the heights and check the ordering yourself, from the nodes.

Recall the two properties from the chapter. The ordering property says every value in a node’s left subtree is smaller than the node and every value in its right subtree is larger, across whole subtrees, not just immediate children. The balance property says every node’s balance factor, the height of its left subtree minus the height of its right, is $-1$, $0$, or $1$.

Here are two trees. Each one fails exactly one of the two properties.

This tree is in search order but not balanced:

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

Every value is in order: $20<30<50$. But 50 has a left subtree of height $1$ and an empty right subtree, so its balance factor is $1-(-1)=2$. You need a balance check to catch this. The ordering check alone says the tree is fine.

This tree is balanced but not in search order:

       ╭────╮
       │ 50 │
       ╰──┬─╯
   ┌──────┴──────┐
╭──┴─╮        ╭──┴─╮
│ 30 │        │ 70 │
╰──┬─╯        ╰────╯
   └─┐
  ╭──┴─╮
  │ 60 │
  ╰────╯

Every node has a balance factor of $-1$, $0$, or $1$, so the balance check passes. But 60 sits in the left subtree of 50, where every value must be smaller than 50, and $60>50$. You need an ordering check to catch this. The balance check alone says the tree is fine.

Your method should run in $O(n)$ time.

Try it before reading the solution.