Validate BST
MediumEvery node within a (min, max) range
Every left value must be smaller and every right value bigger — check each node stays inside its allowed range.
The idea
Recurse carrying the allowed value range. Each node must fall strictly inside (low, high); going left tightens the upper bound, going right tightens the lower bound.
Step 1 of 9. Every node must sit strictly inside an allowed (low, high) range. Left tightens high, right tightens low.
1/9
Optimal
timeO(n)spaceO(h)
Shrink bounds as you descend.
1function valid(node, low, high) {2 if (!node) return true;3 if (node.val <= low || node.val >= high) return false;4 return valid(node.left, low, node.val)5 && valid(node.right, node.val, high);6}Input
- nodes
- 7, 6 edges
Memory
- range
- —
Output
- valid
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [2,1,3]
- Output:
- true
- Explanation:
- Left < root < right everywhere.
Example 2
- Input:
- tree = [5,1,4,null,null,3,6]
- Output:
- false
- Explanation:
- 4 sits right of 5 but is smaller → false.
Example 3
- Input:
- tree = [1]
- Output:
- true
- Explanation:
- A single node is a valid BST.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.