March 24
Validate Binary Search Tree
How to validate a BST by propagating limits through recursion instead of doing local comparisons that look right but break.
Trees Intermediate 20 min TypeScript
Given the root of a binary tree, return true if it is a valid binary search tree and false otherwise.
In a valid BST:
- all nodes in the left subtree are smaller than the current node
- all nodes in the right subtree are larger than the current node
- both subtrees must also be valid BSTs
Example:
Input: [2,1,3]
Output: true
What to notice before coding
- The BST rule is global, not only local.
- Duplicates make the BST invalid in this problem.
- A node can respect its parent and still violate a limit coming from above.
Common mistakes
- comparing each node only with its direct parent
- allowing equal values on the left or right
Step 1 - See where the local check lies to you
Many people start with:
- left smaller than parent
- right larger than parent
It sounds right.
But it is not enough.
A node can respect its direct parent and still violate the root higher up.
Step 2 - Write a baseline that makes that clearer
A valid baseline is:
- do an inorder traversal
- store the values in an array
- check whether the sequence is strictly increasing
It works because inorder traversal of a valid BST comes out sorted.
Step 3 - Ask what restriction each node really carries
Each node does not inherit only the parent.
It inherits a whole interval of valid values.
Example:
- if you entered the right subtree of root
5, everything there must be greater than5 - that keeps being true several levels below
Step 4 - Propagate limits through recursion
So the function can carry:
minmax
And each node must satisfy:
min < node.val < max
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function isValidBST(root) {
// root is an object like { val: number, left: ..., right: ... } or null
// your solution here
return false
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(h)
Solution 1 - Inorder plus order check
Good baseline because it reveals the BST property without falling into the direct-parent trap.
export function isValidBST(root) {
const values = []
function inorder(node) {
if (node === null) {
return
}
inorder(node.left)
values.push(node.val)
inorder(node.right)
}
inorder(root)
for (let index = 1; index < values.length; index += 1) {
if (values[index] <= values[index - 1]) {
return false
}
}
return true
}It works well, but it stores structure you do not really need.
Solution 2 - DFS with limits
Now the global rule becomes part of the recursion.
export function isValidBST(root) {
function validate(node, min, max) {
if (node === null) {
return true
}
if (node.val <= min || node.val >= max) {
return false
}
return validate(node.left, min, node.val) && validate(node.right, node.val, max)
}
return validate(root, -Infinity, Infinity)
}This version captures the core of the problem: each call inherits a valid interval.
What to say in the interview
A strong short explanation would be:
The common mistake is comparing each node only to its parent. The real BST rule is global. So I propagate a valid interval through
recursion. Each node must stay strictly betweenminandmax, and those limits get tighter as I go down the tree. That still visits each node once inO(n).
That shows that you:
- saw the classic failure mode of the bad solution
- modeled the constraint the right way
- explained the global rule clearly
When this pattern shows up again
The same pattern comes back when you need to:
- propagate constraints through
recursion - validate structure with a global rule
- reason with ranges in trees
- solve problems where the grandparent context still matters
The point is not memorizing
isValidBST.
The point is learning when local comparison is not enough.