Validate Binary Search Tree
Last Updated: March 29, 2026
Understanding the Problem
We need to check whether a binary tree satisfies the BST property. At first glance, this seems simple: just check that every node's left child is smaller and right child is larger, right? But that's a trap. The BST property isn't just about immediate children. It's about entire subtrees.
Consider the tree [5,4,6,null,null,3,7]. Node 3 is the left child of 6, so 3 < 6 checks out locally. But node 3 sits in the right subtree of the root (5), and 3 < 5 violates the BST rule. Every node in the right subtree of 5 must be greater than 5, no exceptions.
The key observation is that each node in a BST has an allowable range. As you go left from a node, you tighten the upper bound. As you go right, you tighten the lower bound. A node is valid only if its value falls within its current range.
Key Constraints:
[1, 10^4]nodes → With up to 10,000 nodes, O(n) and O(n log n) approaches are both fine. Even O(n^2) would technically work, but there's no reason for it.-2^31 <= Node.val <= 2^31 - 1→ Values span the full 32-bit integer range. This matters because we can't useInteger.MIN_VALUEorInteger.MAX_VALUEas sentinel bounds. They could be actual node values. We need to useLong.MIN_VALUE/Long.MAX_VALUEor null-based bounds instead.
Approach 1: Brute Force (Check All Ancestors)
Intuition
The most direct way to validate a BST is to check, for every node, that it satisfies the BST property with respect to ALL its ancestors, not just its parent. For a node deep in the left subtree, every ancestor above it on the "left path" imposes an upper bound, and every ancestor on the "right path" imposes a lower bound.
A brute force approach would be: for each node, traverse its entire left subtree and verify every value is less than the node, then traverse its entire right subtree and verify every value is greater. This is simple and correct, but wasteful. We re-examine subtrees over and over.
Algorithm
- For each node in the tree, verify that every node in its left subtree has a smaller value.
- For each node in the tree, verify that every node in its right subtree has a larger value.
- If any node violates this, return false.
- If all nodes pass, return true.
Example Walkthrough
Input:
At node 5: check left subtree (node 1) — all values less than 5? Yes. Check right subtree (nodes 4, 3, 6) — all values greater than 5? Node 4 is not greater than 5. Return false.
Code
- Time Complexity: O(n^2). For each node, we potentially traverse its entire subtree to verify values. In a skewed tree, the root checks all n-1 nodes, then its child checks n-2 nodes, and so on.
- Space Complexity: O(n). The recursion stack can go as deep as the height of the tree, which is O(n) for a skewed tree.
The bottleneck here is redundant work. We re-visit the same nodes multiple times checking the same constraints. What if we could check each node exactly once by carrying the valid range down as we traverse?
Approach 2: Recursive Range Validation (Optimal)
Intuition
Instead of checking upward from each node, we can pass valid bounds downward. Every node in a BST must fall within a specific range. The root can be anything (-infinity to +infinity). When we go left from a node with value v, the new upper bound becomes v. When we go right, the new lower bound becomes v. If a node's value ever falls outside its allowed range, the tree is invalid.
This solves the problem cleanly. When we reach node 3 (left child of 6, which is the right child of 5), its range is (5, 6). Since 3 < 5, it's out of range, and we catch the violation immediately.
The range-based approach encodes the cumulative constraint from every ancestor into just two numbers: a lower bound and an upper bound. Instead of checking a node against all its ancestors (which is what makes the brute force quadratic), we compress all ancestor constraints into the range (lower, upper) that gets passed down. Each node only needs to check itself against these two values, and then pass tighter bounds to its children.
Algorithm
- Start at the root with the range
(-infinity, +infinity). - Check if the current node's value is within
(lower, upper). If not, return false. - Recurse on the left child with the range
(lower, node.val)— the node's value becomes the new upper bound. - Recurse on the right child with the range
(node.val, upper)— the node's value becomes the new lower bound. - If both subtrees are valid, return true.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once and do O(1) work per node (just two comparisons and two recursive calls).
- Space Complexity: O(n). The recursion stack depth equals the height of the tree. For a balanced tree that's O(log n), but for a skewed tree it's O(n).
The time complexity is already optimal, but there's a completely different way to think about this problem. What if we used the fact that an in-order traversal of a valid BST produces a sorted sequence?
Approach 3: In-Order Traversal
Intuition
One of the most useful properties of a BST is that an in-order traversal (left, root, right) visits nodes in strictly ascending order. If we perform an in-order traversal and at any point the current value is not strictly greater than the previous value, the tree is not a valid BST.
This approach doesn't need to track ranges at all. We just need one variable: the value of the last node we visited. If the current node's value is less than or equal to the previous value, we've found a violation.
Algorithm
- Perform an in-order traversal of the tree (left, root, right).
- Keep track of the previously visited node's value.
- At each node, check if the current value is strictly greater than the previous value.
- If not, return false.
- If the traversal completes without violations, return true.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once during the in-order traversal.
- Space Complexity: O(n). The recursion stack depth equals the height of the tree, which is O(n) in the worst case for a skewed tree and O(log n) for a balanced tree.