Given the root of a binary tree, decide whether it is a valid binary search tree (BST).
A valid BST requires, at every node: all values anywhere in the left subtree are strictly less than the node's value, all values anywhere in the right subtree are strictly greater, and both subtrees are themselves valid BSTs. Duplicates are not allowed.
Examples
root = [2, 1, 3]true1 < 2 < 3, and both subtrees are trivially valid.
root = [5, 1, 4, null, null, 3, 6]false4 sits in 5's right subtree, but 4 < 5. The violation is between a node and its *grandparent*, not its parent.
root = [5, 4, 6, null, null, 3, 7]falseEvery parent-child pair looks fine locally (4 < 5, 6 > 5, 3 < 6, 7 > 6), but 3 lives in 5's right subtree while being less than 5. This is the case that kills the naive check.
Constraints
1 ≤ number of nodes ≤ 10⁴-2³¹ ≤ Node.val ≤ 2³¹ − 1
The explainer is the good part.
Sign in for the full intuition build-up, every approach from naive to optimal with complexity analysis, progressive hints, and commented solutions in Python, JavaScript, and Java. All free.
Want a taste first? Try a free sample: Two Sum or Valid Parentheses.