Validate Binary Search Tree
Problem Statement
Given the root of a binary tree, determine whether it is a valid binary search tree. A valid BST requires every node in the left subtree to be strictly smaller than the current node, every node in the right subtree to be strictly larger, and both subtrees to obey the same rule.
Input
The root pointer of a binary tree whose nodes store integer values.
Output
A boolean: true if the tree satisfies the strict BST ordering rule, otherwise false.
Constraints
- •
1 <= number of nodes <= 10^4 - •
-2^31 <= Node.val <= 2^31 - 1
Examples
Example 1
root = **[2,1,3]**
**true**Example 2
root = **[5,1,4,null,null,3,6]**
**false**Example 3
root = **[2,2,2]**
**false**Learning Objectives
- Explain why checking only a node against its direct children is not enough for BST validation.
- Carry an exclusive **low** and **high** value range through recursive subtree calls.
- Use inorder traversal as an equivalent strictly-increasing validation strategy.
- Handle integer boundary values safely with **Long** or nullable bounds.
Intuition
Pattern Recognition
The signal is any prompt that asks whether a binary tree is a valid BST. A BST is not just local parent-child ordering. Every node inherits constraints from all ancestors, so a value deep in the left subtree of 5 must still be less than 5, even if it is greater than its immediate parent.
The classic trap is checking only node.left.val < node.val < node.right.val. That misses violations that appear lower in the subtree. The reliable pattern is BST -> compare and branch, inorder is sorted: either pass down an exclusive low, high range during DFS, or perform inorder traversal and require the visited values to be strictly increasing.
Common mistakes
- ×Checking only direct children and ignoring ancestor bounds.
- ×Allowing duplicate values even though the LeetCode BST definition is strict.
- ×Using **Integer.MIN_VALUE** and **Integer.MAX_VALUE** sentinels, then failing when a node has an extreme value.
- ×Using preorder or postorder values as if they must be sorted; only inorder has the sorted property for a BST.
Algorithm Explanation
Key idea
Every recursive call receives the open interval of values that subtree is allowed to contain. The root can be anywhere, so it starts with no lower or upper bound. When moving left, the current node becomes the new upper bound. When moving right, the current node becomes the new lower bound. A node is valid only if it is strictly inside its inherited range.
Recursion walkthrough
Use the tree [5,3,8,2,6,7,9]. A direct-child check might accept 6 because it is the right child of 3 and 6 > 3. The range method catches the real problem. Start at 5 with no bounds. Move left to 3, whose valid range is less than 5. Move right to 6, whose valid range is greater than 3 and less than 5. The value 6 breaks the upper bound 5, so the whole tree is invalid.
For a valid tree like [5,3,8,2,4,7,9], the call at 4 carries the range greater than 3 and less than 5, which 4 satisfies. The call at 7 carries greater than 5 and less than 8, which 7 satisfies. Every node respects the bounds inherited from its ancestors.
Algorithm
- Start DFS at root with low = null and high = null.
- If the current node is null, return true because an empty subtree is valid.
- If low exists and node.val <= low, return false.
- If high exists and node.val >= high, return false.
- Validate the left subtree with the same low and high = node.val.
- Validate the right subtree with low = node.val and the same high.
- Return true only if both subtrees are valid.
Correctness reasoning
The range carried into each call represents exactly the restrictions imposed by all ancestors. The current node must satisfy those restrictions before its children can be considered. Updating the upper bound on the left and the lower bound on the right preserves the BST rule for every descendant. Therefore, if the DFS returns true, every node is inside the correct ancestor range; if any node violates the BST definition, it eventually appears in a call whose range excludes it and the DFS returns false.
Solutions
Solution 1: Range DFS with nullable Long bounds
Use this as the primary interview solution. It states the global BST invariant directly, avoids integer-edge sentinels, and works naturally with recursion.
Carry an exclusive lower and upper bound into each subtree. The left child tightens the upper bound to the current value, and the right child tightens the lower bound to the current value.
Step-by-step
- Call the helper with root, null lower bound, and null upper bound.
- Return true for a null node.
- Reject the node if it is not strictly greater than the lower bound or not strictly less than the upper bound.
- Recurse left with the current value as the new upper bound.
- Recurse right with the current value as the new lower bound.
- Return the logical AND of the two subtree validations.
O(n)
O(h)
Every node is visited once. The recursion stack is O(log n) for a balanced tree and O(n) for a skewed tree.
Java implementation
Solution 2: Iterative inorder increasing check
Use this when you want to lean on the sorted-order property of BST inorder traversal. It is also useful if the interviewer asks for an iterative version.
Traverse nodes in inorder order with an explicit stack. In a valid BST, each visited value must be strictly greater than the previous visited value.
Step-by-step
- Push left ancestors until reaching null.
- Pop the next inorder node from the stack.
- Compare its value with the previous inorder value, rejecting if it is not strictly larger.
- Store the current value as previous.
- Continue with the current node right subtree.
- If traversal finishes without a violation, return true.
O(n)
O(h)
The traversal visits each node once. The stack is O(log n) for a balanced tree and O(n) for a skewed tree.
Java implementation
Dry Run
Sample input
root = [5,3,8,2,6,7,9]. The node 6 sits in the left subtree of 5, so it must be less than 5 even though it is greater than 3.
| step | node | valid range | decision | next recursive work |
|---|---|---|---|---|
| 1 | 5 | no lower bound, no upper bound | 5 is allowed | check left with upper bound 5 and right with lower bound 5 |
| 2 | 3 | less than 5 | 3 is allowed | check left with upper bound 3 and right with range greater than 3 and less than 5 |
| 3 | 2 | less than 3 | 2 is allowed | both children are null, return true for this branch |
| 4 | 6 | greater than 3 and less than 5 | 6 violates the upper bound 5 | return false immediately |
The failure is found at 6 because ancestor 5 still constrains the entire left subtree. A direct-child-only check would miss this violation.
Interview Tips
Say the global invariant first: every node must be inside the range created by all ancestors, not only by its parent. Then mention the alternative: inorder traversal of a BST is strictly increasing. If node values can be Integer.MIN_VALUE or Integer.MAX_VALUE, use Long or nullable bounds instead of integer sentinels.
Likely follow-ups
- How would the validation change if duplicates were allowed on one chosen side?
- Can you validate the BST iteratively without recursion?
- How would you find the first pair of swapped nodes in a nearly valid BST?
- How would you validate a stream of preorder values as a possible BST preorder traversal?
Similar Problems
Key Takeaways
- A valid BST is governed by ancestor ranges, not just parent-child comparisons.
- Range recursion passes exclusive **low** and **high** bounds downward.
- Inorder traversal is a second optimal test because BST values appear strictly increasing.
- Nullable **Long** bounds avoid edge failures at integer extremes.