Solution: Carrying Bounds Down the Recursion

A first idea is to compare each node only against its immediate children. Here is that local check in code:

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

On the invalid tree from the problem statement, every parent-child pair is in order, so localCheck returns true even though the tree is not a valid BST.

The local check fails because it ignores the ancestors. The recursive call needs to remember more than the parent. It needs the full range of values allowed at this position.

At the root, there is no lower or upper bound. In the left subtree of 50, every value must be less than 50. In the right subtree of 50, every value must be greater than 50.

Carry those bounds down:

public static <T extends Comparable<T>> boolean isValidBst(Node<T> root) {
  return isValidBst(root, null, null);
}

private static <T extends Comparable<T>> boolean isValidBst(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 isValidBst(node.left, min, node.value)
      && isValidBst(node.right, node.value, max);
}

The bounds are open bounds. If min is not null, the node’s value must be strictly greater than min. If max is not null, the node’s value must be strictly smaller than max.

When we go left, the current node becomes the new upper bound:

isValidBst(node.left, min, node.value)

When we go right, the current node becomes the new lower bound:

isValidBst(node.right, node.value, max)

Trace the invalid tree as a call stack. Each frame carries the open range its node must fall in. The range shown in the frame is exactly the (min, max) the call received.

At the root the range is unbounded. 50 fits, so we recurse left, and 50 becomes the new upper bound.

call stack

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ isValidBst(node=50)  range (-inf, inf) ┃
        ┃   waiting for isValidBst(50.left)      ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

tree

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

30 must fall in $(-\infty ,50)$. It does. Its own left child is null, which always passes, so we recurse right, and 30 becomes the new lower bound.

call stack

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

tree

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

Now 60 must fall in $(30,50)$. It passes the lower bound but not the upper one: $60\ge 50$. This frame returns false.

call stack

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ isValidBst(node=60)  range (30, 50)      ┃
        ┃   return false  (60 >= 50, out of range) ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
        ┌──────────────────────────────────────────┐
        │ isValidBst(node=30)  range (-inf, 50)    │
        │   waiting for isValidBst(30.right)       │
        ├──────────────────────────────────────────┤
        │ isValidBst(node=50)  range (-inf, inf)   │
        │   waiting for isValidBst(50.left)        │
        └──────────────────────────────────────────┘

tree

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

The false propagates back up. The && in isValidBst(30) is now false, so it returns false.

call stack

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ isValidBst(node=50)  range (-inf, inf) ┃ ◀── receives false
        ┃   waiting for isValidBst(50.left)      ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

tree

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

isValidBst(50)'s left operand is false, so the && short-circuits: the right child 70 is never checked, and the method returns false.

call stack

        (empty — all calls have returned)

tree

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

There is another good solution. Do an in-order traversal and check that each value is larger than the one before it. This works because the in-order traversal of a valid binary search tree comes out in strictly increasing order.

The bounds solution visits each node once, so the time cost is $O(n)$. The recursion stack uses $O(h)$ space, where $h$ is the tree height.