← Back to DSA Animator
Validate Binary Search Tree LC #98 Medium DFS · Range Narrowing
Problem

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST requires every node in the left subtree to have a value strictly less than the node, every node in the right subtree to have a value strictly greater than the node, and both subtrees must also be valid BSTs.

Example 1
Input: root = [2,1,3]
Output: true
Explanation: 1 < 2 < 3 — all BST properties satisfied.
Example 2
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: Root's right child is 4, but 4 < 5 — violates BST property.
Constraints: 1 ≤ nodes ≤ 104  |  −231 ≤ Node.val ≤ 231−1
Try Examples
Custom:
Approach
DFS with Shrinking Valid Range
Pass down a valid range (min, max) at each level. Going LEFT narrows the max to node.val. Going RIGHT narrows the min to node.val. Any node.val outside its range makes the tree invalid.
Valid Range Indicator
Current valid range for the node being checked
min bound
−∞
 < 
node.val
—
 < 
max bound
+∞
— Waiting to check a node…
Binary Tree
Processing
Valid
Invalid
Visited
Unvisited
DFS Call Stack
Stack is empty — not started
Variables
Node.val
—
min bound
—
max bound
—
valid?
—
Call Trace
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Call validate(root, −∞, +∞) — root starts with the full valid range
2
node == null → return true (null is trivially valid)
3
node.val ≤ min OR node.val ≥ max → return false (range violation)
4
Recurse: left with (min, node.val), right with (node.val, max) — range narrows each level
Time
O(n)
Space
O(h)
Why Range Narrowing Works

A common mistake is only checking the immediate parent-child relationship. That misses deeper violations — e.g., a node in the right subtree that is smaller than the root. By threading the valid range (min, max) down each call, every node carries the full historical constraint from all its ancestors. Going left means the current value becomes the new ceiling; going right it becomes the new floor. The check is globally correct in a single O(n) pass.