Validate Binary Search Tree

Difficulty: Medium

Problem

Decide whether the binary tree rooted at root is a valid binary search tree (BST). For every node, ALL values in its left subtree must be strictly LESS than the node and ALL values in its right subtree strictly GREATER, and each subtree must itself follow the same rule. Checking only a node's immediate children is the classic mistake.

Example

Input: root = [5,4,6,null,null,3,7]
Output: false
Explanation: Node 3 looks fine next to its parent 6 (3 < 6 ✓). But 3 sits inside 5's RIGHT subtree, where everything must be GREATER than 5, and 3 isn't. Not a BST.

Brute-force approach

The tempting parent-child-only check is not a slower solution, it's a WRONG one. The lesson shows exactly how it fails, then fixes it with ranges.

Optimal approach

Key insight: Every turn you take on the way down leaves a promise. The (lo, hi) range remembers ALL of them. One comparison per node checks every ancestor at once.

Pass an allowed (lo, hi) range down the tree. Each node must sit strictly inside its range; going left tightens the ceiling, going right raises the floor.

Steps

  1. Start at the root with the wide-open range (-∞, +∞)
  2. At each node check: lo < node.val < hi; if not, return false
  3. Recurse left with (lo, node.val), the ceiling drops
  4. Recurse right with (node.val, hi), the floor rises
  5. Null subtrees are valid (they break no promises)

Time complexity: O(n) · Space complexity: O(h) where h = height of tree

Pseudocode

function isValidBST(root):
    function check(node, lo, hi):
        if node is null:
            return ____
        if not (____ < node.val < ____):
            return false
        return check(node.left, lo, ____) and
               check(node.right, ____, hi)
    
    return check(root, ____, ____)

Hints

  • An empty subtree contains no values, can it break any promise?
  • The node must sit strictly INSIDE its inherited range, which two bounds?
  • Going left, the CEILING becomes this node's value; going right, the FLOOR does
  • The root has no ancestors. Start with the widest possible range

Complexity questions

What is the time complexity of the range-narrowing solution?

O(n): every node is checked exactly once against its range. Each node does one O(1) range comparison and hands narrowed ranges to its children. One traversal → O(n).

What is the space complexity?

O(h): the recursion stack, each frame holding two numbers. Only the recursion stack: O(log n) balanced, O(n) skewed. The two range numbers per frame are constant space.

Why does 'the inorder traversal comes out strictly increasing' also prove a valid BST?

Inorder visits left-subtree, node, right-subtree, in a BST that's smallest to largest, so any violation shows up as a non-increasing adjacent pair. Inorder on a BST produces sorted output (you learned this in the traversals lessons!). The converse holds too: if inorder is strictly increasing, the BST property holds everywhere. Same O(n), different style.

Why does [1,1] (root 1 with left child 1) fail validation?

The inequalities are STRICT: the left child must be < its ancestor, and 1 < 1 is false. The left child inherits range (-∞, 1) and must satisfy val < 1. A duplicate 1 fails. Under this problem's definition, equal values anywhere in a subtree make the tree invalid.

Check your understanding of Validate Binary Search Tree

What exactly does the BST property require?

The ENTIRE left subtree < node < the ENTIRE right subtree, at every node. It's about whole subtrees, not just direct children. Every single value anywhere in the left subtree must be smaller; every value in the right subtree must be greater. The immediate-children version is the famous WRONG answer.

In [5,4,6,null,null,3,7], node 3 satisfies 3 < 6 with its parent. Why is the tree still invalid?

Because 3 lives inside 5's RIGHT subtree, so it must be GREATER than 5: ancestors' rules reach all the way down. When we turned RIGHT at 5, we promised: everything below is > 5. Node 3 breaks that promise made two levels up. Parent-child checks alone can never catch this.

How can we carry EVERY ancestor's constraint using just two numbers?

An allowed open range (lo, hi): the node must satisfy lo < val < hi. Each turn on the way down narrows the range. By the time we reach any node, (lo, hi) summarizes every promise made above it. One comparison checks them all at once.

Going LEFT from a node with value v, how does the child's allowed range change?

The ceiling drops: (lo, v), everything left of v must be smaller than v. Turning left promises 'smaller than v', so the ceiling tightens to v: (lo, v). Symmetrically, turning right raises the floor: (v, hi).

What range does the root start with?

(-∞, +∞): no promises made yet. The root has no ancestors, so nothing constrains it: any value is allowed. Constraints only accumulate as we descend and turn.

Related problems

Keep practising