MediumDepth-First SearchBinary Search TreeTreeUpdated Sep 2026

98. Validate Binary Search Tree

Asked at Google, Meta, Amazon, Microsoft and 3 more

Difficulty

Medium

Time

O(n)

Space

O(h)

Pattern

Depth-First Search

Companies

7

Problem

You are given the root of a binary tree. Decide whether this tree is a valid binary search tree (BST).

A tree is a valid BST when, for every node, all values in its left subtree are strictly smaller than the node's value, and all values in its right subtree are strictly larger. Both subtrees must also be valid BSTs. Note the word strictly: equal values are not allowed anywhere on the wrong side.

A common trap is to check only each node against its own children. That is not enough — a node must also respect every ancestor above it. Return true if the tree is a valid BST, otherwise false.

Why parent-child checks are not enough

15root = 5344 < 5 → bad64 lives in the right subtree of 5, so it must begreater than 5 — it is not.
Node 4 is a right child of 5, but it is smaller than 5, so the whole tree fails.

Constraints

  • ●The number of nodes is in the range [1, 10^4].
  • ●-2^31 <= Node.val <= 2^31 - 1.

Examples

Example 1
Inputroot = [2,1,3]
Outputtrue
WhyThe root is 2. Its left child 1 is smaller than 2, and its right child 3 is larger than 2. Both children are leaves, so every rule holds.
Example 2
Inputroot = [5,1,4,null,null,3,6]
Outputfalse
WhyNode 4 sits in the right subtree of 5, so it must be greater than 5. But 4 < 5, so the tree is not a valid BST. Checking only 5 against its children misses this.

Asked At

7 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MetaMediumView all Meta questions →
AmazonMediumView all Amazon questions →
MicrosoftMediumView all Microsoft questions →
AppleMediumView all Apple questions →
NetflixMediumView all Netflix questions →
AtlassianMediumView all Atlassian questions →

How to Think About It

1

Common mistake: only checking parent-child relationships. A node must be less than ALL ancestors on the right, not just its parent.

2

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.

3

Alternative: in-order traversal of a valid BST produces a strictly increasing sequence. Track the previous value and verify each node is larger.

4

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.

Pass down an allowed range

15(-inf, inf)346The root may be any value, so its range is (-inf,inf).1(-inf, 5) ok534(5, inf) fails6Going left tightens max to 5; going right tightens minto 5. Node 4 breaks the right range.check: min < node.val < maxleft: (min, node.val)right: (node.val, max)
Each node must fall strictly inside the open range (min, max) handed down by its ancestors.
ComplexityTime O(n)Space O(h)Each node is checked once; the extra space is the recursion stack, whose depth is the tree height h.

What Trips People Up in Real Interviews

1

Only checking parent-child relationships. A node must be valid relative to ALL ancestors, not just its parent. Use min/max bounds.

2

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).

3

Not handling the case where the tree has duplicate values. The problem says strictly less/greater, not less-or-equal.

4

Using in-order traversal and checking adjacent nodes. This works but is less intuitive than the bounds approach. Both are O(n).

5

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

O(n) time
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'))

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

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 runs in O(n) time and O(h) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.