Validate Binary Search Tree

Why it belongs on this sheet

This problem is important because the tempting local check is wrong. Interviewers like it for that reason.

Pattern

Allowed value range

Approach

Carry a lower and upper bound down the recursion. Every node must stay strictly between those bounds.

Java solution

class Solution {
  public boolean isValidBST(TreeNode root) {
    return validate(root, null, null);
  }

  private boolean validate(TreeNode node, Long lower, Long upper) {
    if (node == null) {
      return true;
    }

    if ((lower != null && node.val <= lower) || (upper != null && node.val >= upper)) {
      return false;
    }

    return validate(node.left, lower, (long) node.val)
      && validate(node.right, (long) node.val, upper);
  }
}

Complexity

• Time: O(n)
• Space: O(h)

Interview note

The whole point is that validity depends on ancestors, not just the direct parent.