Validate Binary Search Tree
Problem
root of a binary tree, decide whether it is a valid BST:
every value in a node's left subtree is strictly smaller than the node, every value in
its right subtree is strictly larger, and both subtrees are themselves valid BSTs.root = [2,1,3]Outputtrueroot = [5,1,4,null,null,3,6]Outputfalseroot = [5,4,6,null,null,3,7]Outputfalse1 ≤ n ≤ 104 · -231 ≤ Node.val ≤ 231-1 · duplicates make it invalid
Try it yourself
class Solution {
public boolean isValidBST(TreeNode root) {
}
}
Instinct The tree is a BST? Its in-order walk is a sorted list and every node splits the search space - think "sorted array in tree form", not "visit everything".
Memory hack Left is less, right is more, in-order reads the sorted score - and every node lives inside a (low, high) fence set by its ancestors.
Open the Binary Search Tree & In-order guide →Approaches
Brute ForceIn-order into a List, then Scan
O(n)Space O(n)Collect all values with a recursive in-order walk. A tree is a BST exactly when that list is strictly increasing, so check each adjacent pair; an equal pair (duplicate) also fails.
public boolean isValidBST(TreeNode root) { List<Integer> vals = new ArrayList<>(); inorder(root, vals); for (int i = 1; i < vals.size(); i++) { if (vals.get(i) <= vals.get(i - 1)) return false; } return true; } private void inorder(TreeNode node, List<Integer> vals) { if (node == null) return; inorder(node.left, vals); vals.add(node.val); inorder(node.right, vals); }
Simple and correct, but always stores all n values and never stops early.
BetterIterative In-order with prev
O(n)Space O(h)We only ever compare a value with the one just before it, so keep a single
prev instead of the whole list. An explicit stack drives the in-order
walk and we return false at the first non-increasing step.
public boolean isValidBST(TreeNode root) { Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode curr = root; Integer prev = null; // null = nothing visited yet while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); if (prev != null && curr.val <= prev) return false; prev = curr.val; curr = curr.right; } return true; }
O(h) memory and early exit; a bit more code than the recursive bounds check.
OptimalDFS with (low, high) Bounds
O(n)Space O(h)Every node must lie in an open interval inherited from its ancestors. Going
left tightens the upper bound to the parent's value, going right tightens the lower
bound. Using long bounds lets nodes equal to
Integer.MIN/MAX_VALUE pass.
public boolean isValidBST(TreeNode root) { return valid(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean valid(TreeNode node, long low, long high) { if (node == null) return true; if (node.val <= low || node.val >= high) return false; return valid(node.left, low, node.val) && valid(node.right, node.val, high); }
Same complexity, but local, stateless and the cleanest to explain.
Integer bounds and use
null to mean “unbounded”.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | In-order into a List, then Scan | O(n) | O(n) |
| Better | Iterative In-order with prev | O(n) | O(h) |
| Optimal | DFS with (low, high) Bounds | O(n) | O(h) |
- Only comparing each node with its direct children — misses deeper violations.
intbounds withInteger.MIN/MAX_VALUEsentinels — fails on those values.- Using
<instead of<=— accepts duplicates like[2,2,2].
- Draw example 3 to show why the local parent-child check is wrong.
- Present both views: interval bounds and strictly increasing in-order.
- Ask whether duplicates are allowed; here they are not.