How do you solve Validate Binary Search Tree?

Implement a recursive DFS helper that takes a node and its valid value boundaries. If the node is null, return true. If the node's value violates the boundaries, return false. Recursively validate the left subtree with updated upper bound and the right subtree with updated lower bound. The initial call uses (-inf, +inf) as boundaries. This approach guarantees O(n) time by visiting each node once and O(h) space for recursion stack, where h is the tree height.

What pattern does Validate Binary Search Tree use?

The Pattern: DFS (Boundary-Constrained Validation) The Heuristic: When validating global ordering constraints in a tree, propagate value boundaries down the recursion to enforce strict inequalities at every node, ensuring local checks respect global BST properties.

Validate Binary Search Tree — DFS

Q: What is the time complexity of Validate Binary Search Tree?

O(n). Each node is visited exactly once in the DFS traversal, and boundary checks are O(1) operations per node.

Problem

Given the root of a binary tree, determine if it is a valid binary search tree (BST) where for every node, all nodes in its left subtree are strictly less than the node's value, and all nodes in its right subtree are strictly greater.

The number of nodes in the tree is in the range [1, 10⁴]
−2³¹ ≤ Node.val ≤ 2³¹ - 1

Example

Input: root = [2,1,3]

Output: true

Starting at the root node with value 2, the algorithm recursively checks the left subtree with an updated upper boundary of 2 and the right subtree with a lower boundary of 2. The left child node 1 is within the valid range (-inf, 2), and the right child node 3 is within (2, inf). Both subtrees are valid BSTs, so the entire tree is valid.

Approach

Straightforward Solution

A naive approach might check only the immediate left and right children for ordering, which fails for deeper violations. This approach is insufficient because it ignores the global ordering constraints imposed by ancestor nodes.

Core Observation

A BST is defined by the strict ordering of node values relative to all nodes in their subtrees, not just their immediate children. This means each node must lie within a valid value range defined by its ancestors.

Path to Optimal

Preview

The key insight is to carry down boundary constraints during a depth-first traversal. Each recursive call receives a valid range (left_boundary, right_boundary) that the current node's value must satisfy…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Implement a recursive DFS helper that takes a node and its valid value boundaries. If the node is null, return true…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each node is visited exactly once in the DFS traversal, and boundary checks are O(1) operations per node.

Space

O(h)

The recursion stack depth corresponds to the height of the tree, which is O(h). No additional data structures proportional to n are used.

Solution

Python

1class Solution:
  def isValidBST(self, root: TreeNode) -> bool:
      
      def is_valid(node, left_boundary, right_boundary):
          if not node:
              return True
          
          if not (left_boundary < node.val < right_boundary):
              return False
          
          return (is_valid(node.left, left_boundary, node.val) and
                  is_valid(node.right, node.val, right_boundary))
13
      return is_valid(root, float("-inf"), float("inf"))

Step-by-Step Solution

1

Define Helper That Validates a Node Within Boundaries

4	`def is_valid(node, left_boundary, right_boundary):`

Objective

To define a recursive helper that checks whether every node stays within the valid value range imposed by its ancestors.

Key Insight

The solution is not just DFS over nodes; it is DFS with propagated constraints. The helper definition makes that contract explicit by taking a node plus a left and right boundary, which is what allows the algorithm to enforce the global BST property rather than only local parent-child ordering.

Interview Quick-Check

Core Logic

Use a helper that receives a node and its valid lower and upper boundaries.

State & Boundaries

The helper contract must be applied consistently to every subtree to enforce global ordering.

Common Pitfalls & Bugs

If the helper only compares a node with its immediate children, deeper BST violations will be missed.

2

Return True for Null Nodes as Base Case

To establish the base case of recursion where a null node is considered valid.

3

Enforce Node Value Within Boundaries to Validate BST Property

To verify that the current node's value lies strictly between the left and right boundaries.

4

Recursively Validate Left and Right Subtrees with Updated Boundaries

To recursively check left and right subtrees, updating boundaries to maintain global BST constraints.

5

Initiate Validation from Root with Infinite Boundaries

To start the recursive validation from the root node with the widest possible value range.

4 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 8 Critical

if not (left_boundary < node.val < right_boundary):

Check if node's value violates the BST boundaries.

This strict inequality check enforces the global BST property that all node values must lie strictly between their allowed boundaries, preventing invalid trees from passing.

Line 9 Critical

return False

Return false if node's value is out of bounds.

Immediate termination upon violation ensures no further unnecessary recursion and guarantees correctness.

Line 11 Critical

return (is_valid(node.left, left_boundary, node.val) and

Recursively validate the left subtree with updated upper boundary.

Passing the current node's value as the right boundary for the left subtree ensures all left descendants are strictly less than the current node, maintaining BST ordering.

Full line-by-line criticality + rationale for all 8 lines available on Pro.

Test Your Understanding

Why must the algorithm pass down updated boundary constraints rather than just comparing a node's value to its immediate children?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Validate Binary Search Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Validate Binary Search Tree drill

or drill a free problem

1	`class Solution:`
2	`def isValidBST(self, root: TreeNode) -> bool:`
3
4	`def is_valid(node, left_boundary, right_boundary):`
5	`if not node:`
6	`return True`
7
8	`if not (left_boundary < node.val < right_boundary):`
9	`return False`
10
11	`return (is_valid(node.left, left_boundary, node.val) and`
12	`is_valid(node.right, node.val, right_boundary))`
13
14	`return is_valid(root, float("-inf"), float("inf"))`