98. Validate Binary Search Tree

MediumTrees and Binary Search TreesDFS carrying (low, high) boundsRange-bounded validation

Validate Binary Search Tree

Given the root of a binary tree, determine whether it is a valid binary search tree: every node's value must be strictly greater than all values in its left subtree and strictly less than all values in its right subtree.

Open official problem prompt ↗

In plain English

Decide if the tree obeys the global BST ordering rule, not just local parent-child comparisons.

Picture it like this

Like checking a nested set of number ranges: every room you enter narrows the allowed values, and each item inside must fit the room's current label.

Example

Input: root = [2, 1, 3]
Output: true
Why: 1 < 2 in the left subtree and 3 > 2 in the right subtree, so BST order holds everywhere.

Constraints

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

Pattern lesson

See the pattern, then code

Range-bounded validation

↗

Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. A node is valid only if it falls strictly inside an open interval; descending left tightens the upper bound to the node's value, descending right tightens the lower bound.

New words, made simpleKnow these before the algorithm

BST property: For every node, all left-subtree values are smaller and all right-subtree values are larger — strictly.
Bound / window: The open interval (low, high) a node's value is permitted to occupy given its ancestors.
In-order traversal: Visiting left, node, right; on a valid BST this yields strictly increasing values.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Compare only with children

Wrong: a deep descendant can violate an ancestor's bound while satisfying its immediate parent.

Check node.left.val < node.val < node.right.val at each node.

Time O(n)Space O(h)

Best choiceBounds-passing DFS

Enforces the full ancestor constraint on every node; clean and correct.

Carry (low, high) down, tightening one side at each step.

Time O(n)Space O(h)

The rule we keep true

Invariant

When valid(node, low, high) is called, every value in node's subtree must lie strictly within (low, high) for the tree to be a BST.

Why this is correct

Reasoning

Moving left means all values must stay below the parent, so high becomes the parent's value; moving right means all values must exceed the parent, so low becomes it. Composing these along a path yields exactly the tightest legal window, and strict comparison rejects duplicates.

The algorithm in three movesSay these aloud before coding

1Start the root with bounds (-inf, +inf)

node 2: (-inf, +inf) OK

2At each node check low < node.val < high

node 1: (-inf, 2) OK

3Recurse left with high updated to node.val

node 3: (2, +inf) OK

4Recurse right with low updated to node.val

5A null node is trivially valid

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readbounds (-inf, +inf)

2 · Ask-inf < 2 < +inf?

3 · Update statepasses

4 · Resultrecurse left with (-inf,2), right with (2,+inf)

Key takeaway

Each node must fit the shrinking value window inherited from its ancestors.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 12-13Null is valid
An empty subtree imposes no constraint, so it passes.
2
Lines 14-15Window check
Strict inequality on both sides rejects out-of-range values and duplicates.
3
Lines 16Tighten and recurse
Left inherits the node as its new upper bound; right inherits it as the new lower bound.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single node is always valid
Duplicate values must fail because comparisons are strict
Values equal to INT_MIN/INT_MAX are handled since bounds start at +/- infinity

Common beginner mistakes

Only comparing a node to its direct children instead of ancestor bounds
Using <= instead of <, wrongly accepting duplicates
Using a fixed integer sentinel that a real node value could equal — use +/- infinity instead

Check your understanding

Why does comparing each node only to its immediate children fail?

PyPython 3 · solution.py

Optimal

1from typing import Optional23# Definition for a binary tree node.4# class TreeNode:5#     def __init__(self, val=0, left=None, right=None):6#         self.val = val7#         self.left = left8#         self.right = right910class Solution:11    def isValidBST(self, root: Optional[TreeNode]) -> bool:12        def valid(node: Optional[TreeNode], low: float, high: float) -> bool:13            if not node:14                return True15            if not (low < node.val < high):16                return False17            return valid(node.left, low, node.val) and valid(node.right, node.val, high)1819        return valid(root, float('-inf'), float('inf'))

Time complexityO(n)Optimized

Space complexityO(h)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftMetaBloomberg

Validate Binary Search Tree

Validate Binary Search Tree

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trees and Binary Search Trees