Problem Statement

Validate Binary Search Tree

A binary tree is a set of connected boxes called nodes. Each node holds a number and can point to up to two children, a left child and a right child. A binary search tree, or BST, is a special kind of binary tree with one rule about where numbers live: everything in a node's left side is smaller than that node, and everything in its right side is bigger. Your job is to look at the whole tree starting from the top node, called the root, and decide if that rule holds everywhere. The full rule: every node in the left subtree must be strictly less than the node, every node in the right subtree must be strictly greater, and the left and right subtrees must each follow the same rule too.

mediumTreeDFSBinary Search TreeTreesTime: O(n) · Space: O(h)

Signals to notice

check if binary search tree is validnode values within rangein-order gives sorted

Brute force first

Check each node only against its parent — misses violations deeper in the tree. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

Pass valid range (min, max) down: each node must be within its allowed range. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `root = [5,1,4,null,null,3,6] (5 -> left 1, right 4; 4 -> left 3, right 6)`

validate(5, -INF, +INF): 5 in range -> recurse left(low=-INF,high=5), right(low=5,high=+INF)
validate(1, -INF, 5): 1 in range -> children null -> returns true
validate(4, 5, +INF): 4 <= low(5) -> VIOLATION, returns false
node 5's right subtree is false, so the AND short-circuits: 5 fails
Insight: 4 is a valid child of 1's sibling locally, but it violates 5's range (must be > 5)
isValidBST returns false

What must stay true

Every node has an allowed range; left children tighten the max, right children tighten the min. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

function isValid(node, low, high):
    if node is null: return true
    if node.val <= low or node.val >= high: return false
    return isValid(node.left, low, node.val)
       and isValid(node.right, node.val, high)
# call: isValid(root, -INF, +INF)

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Only checking immediate parent-child — a node can violate the BST property with a grandparent. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.

Trees Pattern