Faangprep Logo
LoginRegister
Depth-First Search
Medium

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:

  1. The left subtree of a node contains only nodes with keys less than the node's key.
  2. The right subtree of a node contains only nodes with keys greater than the node's key.
  3. 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)

  1. Pass a valid range (min, max) down to each node.
  2. Root range: (-Infinity, +Infinity).
  3. When going Left, update max: (min, node.val).
  4. When going Right, update min: (node.val, max).
  5. If a node's value is not within (min, max), return false.
Interactive Visualization
Step 1 / 3
5
Range (-Inf, +Inf)
1
4
3
6
5
0
1
1
4
2
3
4
3
5
6
6

Node 5. Range: (-Inf, +Inf). OK

1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.
Unlock VisualizerPREMIUM FEATURE

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.

Start Your Premium Prep