#98
Validate Binary Search Tree
Medium Bounds passed down
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether a binary tree is a valid BST: every node is strictly greater than all nodes in its left subtree and strictly less than all in its right subtree.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: is every node within the range its ancestors allow?
Why this works: pass (low, high) down: the left child gets (low, node), the right child gets (node, high).
Example: 5 (1, 4 (3, 6))
4 must be > 5 (right of 5) → fails → false✦Hints open one at a time
Checking only a node against its children is not enough.
Pass down an allowed (min, max) range for each node.
Use long bounds (or null) because node values can equal Integer.MIN_VALUE / MAX_VALUE.
↗Approach
valid(node, lo, hi): node.val must be in (lo, hi). Left child gets (lo, node.val), right child gets (node.val, hi).
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public boolean isValidBST(TreeNode root) {
return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean valid(TreeNode n, long lo, long hi) {
if (n == null) return true;
if (n.val <= lo || n.val >= hi) return false;
return valid(n.left, lo, n.val) && valid(n.right, n.val, hi); // tighten the range
}
}!Common mistake
Comparing only with the direct parent — a deep right descendant of a left child can still be too large.
Complexity
- Time: O(n).
- Space: O(h).
Topic: Binary Search Trees
🎬 Episodes 61–63: video coming soon