Validate Binary Search Tree DSA Solution

Learning Outcome

After this lesson, you should be able to explain why checking only parent-child relationships is not enough for validating a BST.

Problem Statement

Given the root of a binary tree, return true if it is a valid binary search tree. Every node in the left subtree must be smaller than the current node, and every node in the right subtree must be larger.

Input	Output	Why
`[2,1,3]`	`true`	All nodes satisfy BST bounds.
`[5,1,4,null,null,3,6]`	`false`	3 is in the right subtree of 5 but is less than 5.

Brute Force Approach

Check every node only against its direct children.

This catches local violations but misses deeper ancestor-bound violations, so it is logically incomplete.

Optimized Approach

Carry a valid range into each recursive call. A node must be strictly greater than the lower bound and strictly less than the upper bound. Left children tighten the upper bound; right children tighten the lower bound.

Exact Pseudocode

valid(node, low, high):
  if node is null:
    return true
  if node.val <= low or node.val >= high:
    return false
  return valid(node.left, low, node.val)
     and valid(node.right, node.val, high)
return valid(root, -infinity, infinity)

Reference Code

class Solution:
    def isValidBST(self, root):
        def valid(node, low, high):
            if not node:
                return True
            if node.val <= low or node.val >= high:
                return False
            return valid(node.left, low, node.val) and valid(node.right, node.val, high)

        return valid(root, float("-inf"), float("inf"))

Sample Dry Run

Node	Allowed range	Result
5	`(-inf, inf)`	Valid, split bounds
1	`(-inf, 5)`	Valid
4	`(5, inf)`	Valid locally, check children
3	`(5, 4)`	Invalid because 3 is not greater than 5

Complexity

Measure	Value	Reason
Time	O(n)	Each node is checked once.
Space	O(h)	The recursion stack depends on tree height.

Edge Cases

Duplicate values should fail in the strict BST version.
Very small or very large integer values need wide bounds.
Ancestor violations deeper in the tree.

Interview Checklist

Do not check only direct children.
Carry lower and upper bounds through recursion.
Use strict inequalities for the common BST definition.

FAQs

Why do parent-child checks fail?

A node can satisfy its parent but still violate an older ancestor's bound.

Why use long bounds in Java/C++?

Node values may equal integer extremes, so wider bounds avoid false failures.

What is the core pattern?

DFS with inherited range bounds.

Validate Binary Search Tree: Range bounds Pattern