Validate Binary Search Tree

Determine if a binary tree is a valid Binary Search Tree (BST).

10 min read

Solve on LeetCode

Examples

Input:root = [2,1,3]

Output:true

Explain:

Left (1) < 2 < Right (3).

Input:root = [5,1,4,null,null,3,6]

Output:false

Explain:

The root node's value is 5 but its right child's value is 4.

Problem Understanding

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.

Algorithm Strategy

Common Mistake: Just checking left.val < node.val and right.val > node.val is wrong. It fails for deeper levels (e.g., a node in the right subtree might optionally be smaller than the root).

Correct Approach: Range Validation (Top-Down DFS)

Pass a valid range (min, max) down to each node.
Root range: (-Infinity, +Infinity).
When going Left, update max: (min, node.val).
When going Right, update min: (node.val, max).
If a node's value is not within (min, max), return false.

Interactive Visualization

Step 1 / 1

Empty Heap

Initializing...

Custom Input

Watch how the allowed range tightens as we go deeper.

Previous Problem

Path Sum

Next Problem

Diameter of Binary Tree

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.