Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST requires all nodes in the left subtree to be strictly less than the node value and all nodes in the right subtree to be strictly greater. This rule must hold for every subtree.

Why this is worth learning

A node must satisfy constraints from all ancestors, not just its parent. Bounds are a compact representation of those inherited obligations.

Before coding: one-minute experiment

Why is root 10 with right child 15 and that child’s left child 6 not a valid BST?

Function signature

func IsValidBST(root *TreeNode) bool

Inputs / outputs

• root: root of the tree.
• Return: true if the tree is a valid BST, else false.

Example

    2
   / \
  1   3
Output: true

    5
   / \
  1   7
     / \
    3   8
Output: false (the 3 is in the right subtree of 5 but smaller than 5)

Constraints

• 0 <= number of nodes <= 100_000
• node values fit in 32-bit signed int

Core idea (near-solution)

Checking each parent-child inequality misses obligations from earlier ancestors. A node may be smaller than its parent yet still be illegally small in the root's right subtree. One slow baseline checks a node against every ancestor. Compress those constraints instead: retain the strongest lower bound and strongest upper bound. Moving left tightens the upper bound; moving right tightens the lower bound, while preserving the other bound. The intervals are open because equal keys violate this pack's contract. An inorder strict-increase check is a valid alternative with a different state.

Invariant: when you enter a node, all values in this subtree must fall strictly between low and high.

Algorithm (step-by-step)

1. If root is nil, it is valid.
2. Recurse with bounds (-inf, +inf).
3. At each node:
   • If Val is outside bounds, return false.
   • Recurse left with (low, Val) and right with (Val, high).
4. Return true only if both subtrees are valid.

Correctness sketch

For a recursive subtree with allowed open interval (lo,hi), every valid node must lie strictly within that interval. Reject a root outside it. For an accepted root value v, the entire left subtree must lie in (lo,v) and the entire right subtree in (v,hi); passing these intervals preserves both the current-node constraint and every ancestor constraint. Empty subtrees satisfy the condition. Structural induction proves that acceptance implies the strict ordering throughout the whole tree, and any valid BST satisfies every passed bound. The reference uses int64 sentinels outside the stated 32-bit value domain.

Trace (hand walkthrough)

Example input:
    2
   / \
  1   3
Output: true

    5
   / \
  1   7
     / \
    3   8
Output: false (the 3 is in the right subtree of 5 but smaller than 5)

Walk:
- tree1 inorder: 1,2,3 (strictly increasing) -> true
- tree2: root 5 permits its right child only in (5,+inf)
- right child 7 is accepted; its left child must lie in (5,7)
- node 3 is below the inherited lower bound 5 -> false

Pitfalls to avoid

• Accepting equality with a bound. Reject with val <= low || val >= high; the accepted interval is strict.
• Using int bounds that can overflow; prefer int64.

Debugging lens

Test ancestor-bound violations, duplicate values, and 32-bit endpoint values. Strict comparisons reject duplicates. Numeric sentinels are safe here because node values are explicitly 32-bit, not arbitrary int64.

Complexity

• Time: O(n)
• Extra space: O(h) for recursion depth.

Implementation notes (Go)

• Pass lower/upper bounds as int64 to avoid overflow.
• Use strict inequalities: lo < val < hi.

Reconstruction checkpoint

A validator uses int64 minimum and maximum as exclusive sentinels. A new API allows node values across the full int64 range. Construct a valid tree it would reject and derive a bound representation that avoids the collision.

Return to Binary Search Tree · Module quiz