98. Validate Binary Search Tree
mediumAsked at LinearCheck that every node in a binary tree satisfies the BST property. Linear uses this to see if you avoid the common trap of only comparing a node to its direct parent — the BST constraint is global, not local.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Linear loops.
- Glassdoor (2025-12)— Cited in Linear SWE onsite reports as a tree problem that tests global constraint reasoning.
- Blind (2025-11)— Mentioned in multiple Linear interview threads as a medium tree question.
Problem
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.
Constraints
The number of nodes in the tree is in the range [1, 10^4].-2^31 <= Node.val <= 2^31 - 1
Examples
Example 1
root = [2,1,3]trueExample 2
root = [5,1,4,null,null,3,6]falseExplanation: The root node's value is 5 but its right child is 4, which is not > 5.
Approaches
1. Wrong approach: local parent comparison only
Compare each node only to its direct parent. Fails on trees like [5,4,6,null,null,3,7] where node 3 is less than root 5 but in the right subtree.
- Time
- O(n)
- Space
- O(n)
// INCORRECT — shown to illustrate the common mistake
function isValidBST_WRONG(root) {
function dfs(node, parent, isLeft) {
if (!node) return true;
if (isLeft && node.val >= parent.val) return false;
if (!isLeft && node.val <= parent.val) return false;
return dfs(node.left, node, true) && dfs(node.right, node, false);
}
return dfs(root.left, root, true) && dfs(root.right, root, false);
}Tradeoff: Incorrectly validates [5,4,6,null,null,3,7] as a BST even though 3 is in the right subtree of 5. The BST constraint is global — every node has a valid range inherited from all ancestors.
2. Valid range propagation (optimal)
Recurse with a [min, max] valid range for each node. A node is valid only if min < node.val < max. Narrow the range as you descend.
- Time
- O(n)
- Space
- O(n)
function isValidBST(root) {
function validate(node, min, max) {
if (!node) 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);
}Tradeoff: O(n) time, O(n) stack space. Using -Infinity/Infinity as initial bounds avoids integer edge cases cleanly. Note the strict inequalities — BSTs do not allow duplicate values.
Linear-specific tips
Lead by pointing out the trap: 'The naive approach only compares a node to its parent, which misses global violations. I need to pass down a valid range [min, max] for each subtree.' Linear interviewers specifically test whether you arrive at this insight independently — it's the key intellectual moment for this problem.
Common mistakes
- Only comparing to the direct parent — the BST constraint applies to all ancestors, not just the immediate parent.
- Using <= or >= instead of strict < and > — BSTs do not allow equal values; duplicates make a tree invalid.
- Initializing with integer min/max values — Node.val can equal Integer.MIN_VALUE or MAX_VALUE, so use -Infinity and Infinity.
Follow-up questions
An interviewer at Linear may pivot to one of these next:
- Kth Smallest Element in a BST (LC 230) — in-order traversal naturally gives sorted order.
- Insert into a Binary Search Tree (LC 701) — BST insertion without rebalancing.
- What if the tree allows duplicate values? How does the validity rule change?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why -Infinity and Infinity instead of null?
They work as natural bounds without requiring null checks in the comparison. Node.val can be Integer.MIN_VALUE or MAX_VALUE, so null/sentinel values might clash — Infinity avoids this.
Why are the inequalities strict?
By definition, a BST requires left < root < right with no equality. A node equal to its ancestor is invalid.
Can you solve this with in-order traversal?
Yes — in-order traversal of a valid BST produces a strictly increasing sequence. Track the previous value and check that each new value is strictly greater. Same O(n) complexity.