Trees · LC #98
Validate Binary Search Tree
Validate that a binary tree satisfies BST properties across all levels, not just immediate parent-child. Pass propagating min/max bounds down the recursion to catch violations deep in subtrees.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST satisfies: the left subtree of a node contains only nodes with keys strictly less than the node's key; the right subtree contains only nodes with keys strictly greater; both subtrees are also valid BSTs.
Sample I/O
Input: [2,1,3] Output: true Input: [5,1,4,null,null,3,6] Output: false (4 in right subtree < 5)
Time: O(n) · Space: O(h)
Intuition
How to Think About It
Intuition
Simple parent-child comparison fails because a node in the right subtree must be greater than ALL its ancestors, not just its immediate parent. Propagating a valid range (lo, hi) downward encodes this global constraint - any node outside its range invalidates the BST.
Core Concept
Recursive helper `validate(node, lo, hi)`: null → true; if node.val <= lo or node.val >= hi → false; recurse left with `(lo, node.val)` (upper bound tightens) and right with `(node.val, hi)` (lower bound tightens). Start with `(-∞, +∞)`. Alternatively, inorder traversal must produce a strictly increasing sequence.
When to use
Any BST validation, finding where BST property breaks, recovering swapped BST nodes.
When NOT to use
When you only need to check immediate parent-child relationships (simpler but incorrect for full BST validation).
Key Insights
What to Know Cold
- Bounds propagation catches violations that local parent-child checks miss.
- Use Long.MIN_VALUE/MAX_VALUE in Java or -Infinity/Infinity to handle edge values like Integer.MIN_VALUE.
- Strict inequalities: left < node < right (equal values are invalid in a standard BST).
- Inorder alternative: collect values and check strictly increasing - same O(n) but uses O(n) space.
- When going left, the node's value becomes the new upper bound; when going right, it becomes the lower bound.
1 example
Worked Examples
Hidden violation in right subtree
[5,1,4,null,null,3,6] - node 4 in right subtree is less than root 5.
validate(5, -∞, +∞). Right: validate(4, 5, +∞) → 4 <= 5 → false. Propagated bound catches it.
function isValidBST(root: TreeNode | null): boolean {
function validate(node: TreeNode|null, lo: number, hi: number): boolean {
if (!node) return true;
if (node.val <= lo || node.val >= hi) return false;
return validate(node.left, lo, node.val) && validate(node.right, node.val, hi);
}
return validate(root, -Infinity, Infinity);
}Output: false
Classic trap: checking only [1<5, 3<4<6] passes locally but fails globally.