Validate Binary Search Tree
Asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Atlassian
Problem
Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST has left subtree values strictly less than the node and right subtree values strictly greater.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
| Netflix | Medium | View all Netflix questions → |
| Atlassian | Medium | View all Atlassian questions → |
How to Think About It
Common mistake: only checking parent-child relationships. A node must be less than ALL ancestors on the right, not just its parent.
Pass down a valid range (min, max) to each recursive call. The root gets (-inf, inf). When going left, max becomes node.val. When going right, min becomes node.val.
Alternative: in-order traversal of a valid BST produces a strictly increasing sequence. Track the previous value and verify each node is larger.
Visual walkthrough for tree: 5
/ \n 1 4
/ \n 3 6
Validate(5, -inf, inf) → valid
Validate(1, -inf, 5) → valid (1 < 5)
Validate(4, 5, inf) → 4 < 5? No! 4 is not > 5. Invalid!
The right subtree of 5 has node 4, which is less than 5. That violates BST property.
Edge cases: single node (valid), equal values (invalid — must be strictly less/greater), INT_MIN and INT_MAX values.
Optimal Approach
Approach 1 — Range validation:
Step 1: Define helper(node, min, max).
Step 2: Base case: null node → return true.
Step 3: If node.val <= min or node.val >= max → return false.
Step 4: Recurse: left with (min, node.val), right with (node.val, max).
Approach 2 — In-order traversal:
Step 1: Do in-order traversal (left, node, right).
Step 2: Track previous value. Each node must be > previous.
Step 3: If any node violates this → not a BST.
Time: O(n). Space: O(h) where h is tree height.
What Trips People Up in Real Interviews
Only checking parent-child relationships. A node must be valid relative to ALL ancestors, not just its parent. Use min/max bounds.
Confusing "left subtree values < node" with "left subtree values < node for all ancestors." The left child of the root must be less than the root, but also greater than the root's left bound (negative infinity initially).
Not handling the case where the tree has duplicate values. The problem says strictly less/greater, not less-or-equal.
Using in-order traversal and checking adjacent nodes. This works but is less intuitive than the bounds approach. Both are O(n).
Passing the wrong bounds when recursing right. When going right, the new min should be node.val (exclusive), not node.val + 1. BST requires strictly greater, so the bound is exclusive.
Solution Code
def isValidBST(root):
def dfs(node, min_val, max_val):
if not node:
return True
if node.val <= min_val or node.val >= max_val:
return False
return dfs(node.left, min_val, node.val) and dfs(node.right, node.val, max_val)
return dfs(root, float('-inf'), float('inf'))Frequently Asked Questions
What is the Validate Binary Search Tree problem?
Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST has left subtree values strictly less than the node and right subtree values strictly greater.
How do you solve Validate Binary Search Tree?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Validate Binary Search Tree?
Validate Binary Search Tree is asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Atlassian. It is a medium difficulty problem.
What are common mistakes on Validate Binary Search Tree?
- Only checking parent-child relationships. A node must be valid relative to ALL ancestors, not just its parent. Use min/max bounds.
- Confusing "left subtree values < node" with "left subtree values < node for all ancestors." The left child of the root must be less than the root, but also greater than the root's left bound (negative infinity initially).
- Not handling the case where the tree has duplicate values. The problem says strictly less/greater, not less-or-equal.
- Using in-order traversal and checking adjacent nodes. This works but is less intuitive than the bounds approach. Both are `O(n)`.
- Passing the wrong bounds when recursing right. When going right, the new min should be node.val (exclusive), not node.val + 1. BST requires strictly greater, so the bound is exclusive.