Problem: Validating a Binary Search Tree

A binary search tree is not valid just because every node looks correct next to its immediate children. The ordering property has to hold across whole subtrees.

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 isValidBst(Node<T> root) {

}

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

Here is the tree from the section on the ordering property. It passes every parent-child check, but it is not valid, because 60 is in 50’s left subtree and is larger than 50:

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

Think about what information a recursive call needs to carry. One approach is to carry an allowed range down the tree: every node must fall between a lower bound and an upper bound set by its ancestors.

Another approach is to use in-order traversal. If the tree is a valid BST, the values must come out strictly increasing.

Try it before reading the solution.