Validate Binary Search Tree
The Prompt
Given the `root` of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.
Understanding the Problem
A valid BST demands more than each node beating its immediate children: EVERY node in a left subtree must be smaller than the ancestor above it, and every node in a right subtree larger. The classic trap is checking only parent vs. child — a tree can pass that test and still be invalid because of a deep node that violates a distant ancestor's constraint.
The fix is to carry the constraint down: each node must lie in an open interval (low, high). Going left tightens the upper bound to the current value; going right tightens the lower bound. A node outside its inherited range breaks the BST property no matter how it compares with its parent.
The Interview Flow
Interviewer
How do you validate if a binary tree is a BST?
Candidate
A common mistake is to just check if `node.left.val < node.val` and `node.right.val > node.val`. This isn't sufficient because it doesn't check the entire subtree. For example, a right child of a left child must still be less than the root.
Interviewer
Correct. So how do you enforce that global property?
Candidate
I need to pass down constraints to the children. I can use a recursive helper function that takes the current node, a lower bound, and an upper bound. For the root, the bounds are negative and positive infinity.
Interviewer
How do these bounds update as you traverse?
Candidate
When I go to the left child, the node's own value becomes the new upper bound for that subtree. The lower bound remains the same. When I go to the right child, the node's value becomes the new lower bound, and the upper bound stays the same. At each node, I check if its value is within its received `(lower, upper)` bounds. If not, it's an invalid BST.
Interviewer
That's a very robust recursive solution. It correctly validates the entire tree structure. Please code it.
Why do narrowing ranges catch every violation?
The invariant: a subtree is a valid BST within (low, high) iff its root lies strictly inside the interval and both children are valid within their tightened intervals. The interval is exactly the accumulation of every ancestor constraint on the path down, so a deep violation against a far-away ancestor surfaces as a simple range check at that node — no lookback needed.
Each node is checked once against its range: O(n) time, O(h) recursion space. The equivalent alternative — an inorder traversal that must be strictly increasing — is worth mentioning as a second proof of the same fact.
Recursive DFS with Bounds
- Create a recursive helper function, say `isValid(node, lower, upper)`.
- **Inside `isValid`:**
- The base case: if `node` is null, it's a valid subtree, so return `true`.
- Check the current node's validity: if `node.val <= lower` or `node.val >= upper`, it violates the BST property, so return `false`.
- Make the recursive calls for the children, passing the updated bounds:
- - For the left child, the new upper bound is the current node's value: `isValid(node.left, lower, node.val)`.
- - For the right child, the new lower bound is the current node's value: `isValid(node.right, node.val, upper)`.
- Return `true` only if both recursive calls return `true`.
- Start the process by calling `isValid(root, -Infinity, +Infinity)`.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function isValidBST(root) {
function isValid(node, lower, upper) {
if (!node) {
return true;
}
if (node.val <= lower || node.val >= upper) {
return false;
}
return isValid(node.left, lower, node.val) && isValid(node.right, node.val, upper);
}
return isValid(root, -Infinity, Infinity);
}Explanation
Validate [5, 4, 6, null, null, 3, 7] — ranges narrow on the way down until a deep node exposes the flaw.
1The root 5 starts with the unbounded range (−∞, +∞) — trivially fine. Going left will cap values below 5; going right will floor them above 5.
2Level 1 passes: 4 < 5 fits (−∞, 5), and 6 > 5 fits (5, +∞). A parent-child-only check would already be satisfied everywhere in this tree.
3Node 3 inherits (5, 6): it must exceed ancestor 5 yet stay below parent 6. But 3 < 5 — invalid, even though 3 < 6 looks fine locally. Return false.
Complexity Analysis
TIME
O(n)
SPACE
O(h)
Finished working through this one?
Mark it complete to track it on your Data Structures path.