Validate Binary Search Tree

Given the root of a binary tree, return true if it is a valid binary search tree — for every node, all values in its left subtree are strictly smaller and all values in its right subtree are strictly larger.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

Comparing a node only to its children is not enough — the property spans whole subtrees.

A valid BST's inorder traversal is strictly increasing.

Or carry a (low, high) range down: each node must satisfy low < val < high.

Common doubts

A node deep in a subtree can satisfy its parent yet still violate an ancestor's bound — e.g. a small value in a far-right subtree.

Strict — a valid BST has distinct values, so equal neighbours in inorder make it invalid.

Going left, the current node becomes the new upper bound; going right, it becomes the new lower bound.

Interview follow-ups

· What an interviewer asks next.

A postorder pass returning (min, max, size, isBST) per subtree, combining children.

You can, but the range-passing or inorder approach avoids recomputing subtree extremes at every node.

Fun facts

The inorder-must-increase check is why 'kth smallest' and 'validate' feel like the same problem.
The bounds method generalizes to interval trees and range-constrained validations.

Asked at

AmazonMicrosoftFacebookGoogle

Frequently Sometimes Occasionally

Example 1

Input: root = [2, 1, 3]
Output: true
1 < 2 < 3 — a valid BST.

Example 2

Input: root = [5, 1, 4, null, null, 3, 6]
Output: false
4 is in the right subtree of 5 but 4 < 5, violating the BST property.

Constraints

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

The trap here is checking only a node against its immediate children — that's not enough. The invariant is about entire subtrees: a node deep in the left subtree must still be smaller than a distant ancestor. Two clean ways to enforce it: an inorder traversal must come out strictly increasing, or pass a (low, high) range down and require every node to fall strictly inside it.

Prerequisites

Before you start

· Concepts used directly in the solution.

BST invariant. Left subtree < node < right subtree — for the WHOLE subtree, not just children.

Inorder = sorted. A valid BST's inorder traversal is strictly increasing.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Definition

“Strict or non-strict?”

Strict — duplicate values make it invalid.

“Is it enough to compare a node to its children?”

No — a node must be valid relative to all ancestors, not just its parent.

The ideal opening — say it like this

The BST property is about whole subtrees, so I either check that the inorder traversal is strictly increasing, or carry a valid (low, high) range down to each node.

Comparing a node only to its direct children is the classic mistake — it misses violations across subtrees.

Understand the problem

Worked example — [5, 1, 4, null, null, 3, 6]

        5
       / \
      1   4      <- 4 is in 5's RIGHT subtree but 4 < 5 -> INVALID
         / \
        3   6
inorder: 1, 5, 3, 4, 6 -> 5 then 3 breaks increasing -> false

Key observations

1Aha

It's about subtrees, not children

Every node must respect the bounds set by all its ancestors.

2Aha

Inorder must strictly increase

Equivalent check: the inorder sequence has no equal-or-decreasing step.

3Aha

Tighten the bound on the way down

Left child inherits the parent as an upper bound; right child inherits it as a lower bound.

Brute force vs optimal

	Inorder must increase	(low, high) bounds
Idea	Inorder walk; each value > previous	Each node strictly within an inherited range
Time	O(n)	O(n)
Space	O(height)	O(height)

Both are O(n); pick whichever reads clearer to you. Full code is in the Approaches selector below.

Summary

Key takeaway

Validate by whole-subtree bounds — carry a strict (low, high) range down and require low < val < high — or by checking the inorder traversal is strictly increasing. O(n).

valid(node, lo, hi):
    if node is null: return true
    if not (lo < node.val < hi): return false
    return valid(left, lo, node.val) and valid(right, node.val, hi)