Validate Binary Search Tree (LC 98)

Pattern: Tree DFS with Bounds
Difficulty: Medium
Key Concept: In a BST, every node’s value must lie in an open interval (min, max) inherited from ancestors; left child tightens the upper bound, right child tightens the lower bound.

Problem Statement

Given the root of a binary tree, determine if it is a valid BST:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree contains only nodes with keys greater than the node’s key.
• Both subtrees must also be valid BSTs.

Input: root — may be null.
Output: boolean.

Example

    5
   / \
  1   6
     / \
    4   8   ← 4 is left of 6 but > 5 → invalid

Output: false.

Valid BST:

    5
   / \
  1   7
     / \
    6   8

---

1. Algorithm & Pseudocode

Brute force

1. For each node, gather all values in its left subtree and verify every value < node.val; gather all values in right subtree and verify every value > node.val — O(n²).

Pseudocode

function allValues(node, out):
    inorder collect into out

function isBSTBrute(node):
    if node == null: return true
    leftVals = []; rightVals = []
    allValues(node.left, leftVals)
    allValues(node.right, rightVals)
    for v in leftVals: if v >= node.val: return false
    for v in rightVals: if v <= node.val: return false
    return isBSTBrute(node.left) && isBSTBrute(node.right)

Optimal

1. DFS with bounds valid(node, low, high):
   • null → true.
   • If node.val <= low or node.val >= high (use <= / >= with Long sentinels to handle Integer.MIN_VALUE/MAX_VALUE edge), return false.
   • Recurse: left with high = node.val, right with low = node.val.

Pseudocode

function valid(n, low, high):
    if n == null: return true
    if n.val <= low || n.val >= high: return false
    return valid(n.left, low, n.val) && valid(n.right, n.val, high)

return valid(root, -inf, +inf)

Alternative optimal: inorder traversal must be strictly increasing — O(n) time, O(h) space.

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Why “left < root < right” at each node is not enough: A node in the left subtree can still be greater than an ancestor if you only compare immediate children (classic trap).
• Bounds encode all ancestors: The allowed range shrinks as you go deeper; anything outside fails immediately.
• Why long for bounds: If you use Integer.MIN_VALUE as “unbounded low,” a node with value Integer.MIN_VALUE can incorrectly fail val > min checks; use exclusive bounds with values outside int range.

---

3. The Dry Run

Invalid tree

      5
     / \
    1   6
       / \
      4   8

Node	(low, high)	Check	Result
5	(-∞, +∞)	OK	recurse
1	(-∞, 5)	OK	leaves
6	(5, +∞)	OK	recurse
4	(-∞, 6) but must be > 5 → actually call is valid(4, 5, 6)	4 > 5? false for strict BST: 4 <= 5 fails valid when coming from right of 5… Wait, node 4 is left child of 6, so bounds: valid(4, 5, 6) means low=5, high=6. Value 4: 4 <= 5 → invalid

ASCII (subtree under 6 must stay > 5)

        5  (-inf, inf)
       / \
      1   6  (5, inf)
         / \
        4   8
       ^ fails: 4 is not > 5

---

4. Java Solution

Brute Force

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}

class SolutionBrute {
    // Time: O(n^2) worst skewed, Space: O(n) auxiliary lists + O(h) stack
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        if (!allLess(root.left, root.val)) return false;
        if (!allGreater(root.right, root.val)) return false;
        return isValidBST(root.left) && isValidBST(root.right);
    }

    private boolean allLess(TreeNode n, int v) {
        if (n == null) return true;
        return n.val < v && allLess(n.left, v) && allLess(n.right, v);
    }

    private boolean allGreater(TreeNode n, int v) {
        if (n == null) return true;
        return n.val > v && allGreater(n.left, v) && allGreater(n.right, v);
    }
}

Optimal

class Solution {
    // Time: O(n), Space: O(h)
    public boolean isValidBST(TreeNode root) {
        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean valid(TreeNode n, long low, long high) {
        if (n == null) return true;
        if (n.val <= low || n.val >= high) return false;
        return valid(n.left, low, n.val) && valid(n.right, n.val, high);
    }
}

Inorder optimal

class SolutionInorder {
    private Integer prev;

    public boolean isValidBST(TreeNode root) {
        prev = null;
        return inorder(root);
    }

    private boolean inorder(TreeNode n) {
        if (n == null) return true;
        if (!inorder(n.left)) return false;
        if (prev != null && n.val <= prev) return false;
        prev = n.val;
        return inorder(n.right);
    }
}

---

5. The “Java vs. Others” Edge

• Use long or Long sentinels for bounds; Double.NEGATIVE_INFINITY works but is less idiomatic for integer BSTs.
• Integer prev as boxed allows null for “no predecessor yet”; primitive int needs a boolean first flag.
• Inorder with iterator style can be converted to Morris traversal O(1) extra space (advanced).

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute (all left/right checks)	O(n²)	O(n)	Repeated subtree scans
DFS bounds	O(n)	O(h)	One pass; handles int edge cases with long bounds
Inorder	O(n)	O(h)	Strictly increasing check