89. Validate Binary Search Tree

A common bug: "BST = each node bigger than its left child and smaller than its right." That's wrong. A node's value must be greater than every ancestor that has it in its right subtree, and less than every ancestor that has it in its left subtree. Pass an explicit (low, high) bound down and tighten it as you descend.

Why local checks aren't enough

Consider this tree:

      10
     /  \
    5    15
        /  \
       6    20

Node 15 > 10, fine. Node 6 < 15, fine. But 6 is in 10's right subtree, so it must be > 10. The local parent-child check passes; the BST property fails.

Steps

Define dfs(node, lo, hi) returning whether the subtree rooted at node is a valid BST whose values lie strictly inside (lo, hi).

1. Base case: if node is None, return True (an empty subtree is fine).
2. Bound check: if node.val <= lo or node.val >= hi, return False.
3. Recurse with tighter bounds:
   • The left child must be < node.val. So call dfs(node.left, lo, node.val).
   • The right child must be > node.val. So call dfs(node.right, node.val, hi).
4. Both sides must succeed: return their and.

Initial call: dfs(root, -∞, +∞).

Walk-through

The buggy tree above:

dfs(10, -∞, +∞)
  10 ∈ (-∞, +∞) ✓
  dfs(5, -∞, 10)
    5 ∈ (-∞, 10) ✓
    dfs(None, -∞, 5)  → True
    dfs(None, 5, 10)  → True
    return True
  dfs(15, 10, +∞)
    15 ∈ (10, +∞) ✓
    dfs(6, 10, 15)
      6 ∈ (10, 15)?  6 ≤ 10  ✗  return False  ← caught!
    return False
  return False

A correct BST traverses without ever hitting the False branch.

Edge cases

• Empty tree: root is None, returns True.
• Single node: any value works; (lo, hi) = (-∞, +∞).
• Duplicate values: the strict < comparison rejects duplicates. (Some BST variants allow them; the standard problem doesn't.)
• Boundary integer values: float('-inf') and float('+inf') are safer than INT_MIN/INT_MAX when a node could legitimately equal those.

Complexity

• Time: O(n) — every node is visited once.
• Space: O(h) for the recursion stack, where h is the tree height (O(n) worst case for a skewed tree, O(log n) balanced).

import java.util.*;

class Solution {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = val; }
    }

    public boolean isValidBST(TreeNode root) {
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean dfs(TreeNode node, long lo, long hi) {
        if (node == null) return true;
        if (node.val <= lo || node.val >= hi) return false;
        return dfs(node.left, lo, node.val) && dfs(node.right, node.val, hi);
    }
}

An equivalent way to phrase the BST property: an in-order traversal (left, root, right) yields values in strictly increasing order. So we just walk in-order tracking the previously visited value and bail out the first time we see a value that isn't strictly greater.

Why in-order works

In-order traversal of a binary search tree visits nodes in sorted order — that's the defining shape of a BST. So the validation reduces to: does the in-order sequence have any "out of order" adjacent pair?

Steps

Maintain a prev variable (starts at -∞) holding the value of the most recently visited node.

1. Recurse into node.left. If it returns False, propagate False.
2. Compare node.val with prev:
   • If node.val <= prev, return False — the in-order sequence isn't strictly increasing.
3. Update prev = node.val.
4. Recurse into node.right and return its result.

Walk-through

Tree:

      5
     / \
    1   4
       / \
      3   6

In-order traversal yields: 1, 5, 3, 4, 6.

Caught the violation: node 3 appears in 5's right subtree but its value is less than 5.

Why we need <= not <

The problem disallows duplicates. So a tie (node.val == prev) is also a violation. Using <= covers both cases.

Edge cases

• Empty tree: the recursion's base case returns True immediately.
• Skewed tree: O(n) recursion depth — Python's default limit (1000) is fine for typical inputs but be aware on very deep trees.
• Initial prev: Python's float('-inf') is smaller than any int, so the first comparison always passes correctly.

Complexity

• Time: O(n) — every node visited once.
• Space: O(h) for the recursion stack.