LeetCode · #98

Validate Binary Search Tree Solution

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

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #98

🏗️

Pattern

BST — min/max bounds propagation

Given the root of a binary tree, determine if it is a valid BST. A valid BST has: (1) left subtree values strictly less than the node, (2) right subtree values strictly greater, (3) both subtrees are also valid BSTs.

Example

 Input: 5
        / \
       1   4
          / \
         3   6
Output: false // Node 4 is in the right subtree of 5 but 4 < 5 — violation 

Constraints

• 1 ≤ number of nodes ≤ 10⁴ • -2³¹ ≤ Node.val ≤ 2³¹ - 1

Section Two · Approach 1

Inorder Traversal — O(n)

A valid BST's inorder traversal produces a strictly increasing sequence. Traverse inorder and verify each value is greater than the previous.

Alternative approach:

Works well but requires storing the previous value.
The min/max bounds approach is more elegant and doesn't need extra state.

Section Three · Approach 2

Min/Max Bounds — O(n)

Pass valid value bounds down the tree. Each node must fall within (min, max). When going left, update max to current value. When going right, update min to current value.

💡 Mental model: Each node has a "permit range" — it can only hold values within that range. The root's range is (-∞, +∞). Going left narrows the upper bound; going right narrows the lower bound. If any node violates its permit → invalid BST.

Algorithm

Base: null → true (empty subtree is valid).
Check: If node.val ≤ min or node.val ≥ max → false.
Recurse left: validate(left, min, node.val).
Recurse right: validate(right, node.val, max).

🎯 Common trap:

Only checking left.val < root.val misses deep violations.
Node 3 in the example is left of 4 (3 < 4 ✓) but it's in the right subtree of 5 (3 < 5 ✗).
Bounds propagation catches this because node 3's min bound is 5.

Section Four · Trace

Visual Walkthrough

Bounds propagation — [5, 1, 4, null, null, 3, 6]

Section Five · Implementation

Code — Java & Python

Java — Min/Max Bounds

 class Solution {
public boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
private boolean validate(TreeNode node, long min, long max) {
if (node == null) return true;
if (node.val <= min || node.val >= max) return false;
return validate(node.left, min, node.val)
            && validate(node.right, node.val, max);
    }
}

Python — Min/Max Bounds

 class Solution:
def isValidBST(self, root) -> bool:
def validate(node, lo, hi):
if not node: return True if node.val <= lo or node.val >= hi: return False return validate(node.left, lo, node.val) \
and validate(node.right, node.val, hi)
return validate(root, float('-inf'), float('inf'))

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Min/Max Bounds	O(n)	O(h)
Inorder + check sorted	O(n)	O(h)

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single node	`[1]`	Always valid.
Equal values	`[2,2]`	BST requires strict < / >. Equal values are invalid.
INT_MIN/MAX values	`[2147483647]`	Use long for bounds to avoid overflow when comparing to Integer.MAX_VALUE.

⚠ Common Mistake: Only checking direct parent-child relationship: left.val < root.val. This misses cases where a deep-left node in a right subtree violates the BST property with respect to an ancestor. Bounds propagation catches all violations.

← Back to BST problems

LearningTree

LC 98 · Validate Binary Search Tree — Solution & Explanation | DSA Guide