Validate Binary Search Tree

Problem

Database index trees and autocomplete prefix trees rely on the BST ordering property for O(log n) search. A corrupted insertion or deserialization can silently break the ordering invariant without any local node appearing wrong. Given the root of a binary tree, determine if it is a valid BST where every node satisfies the strict ordering property at every level.

    5
   / \
  3   7
 / \
1   4
→ True
 
    5
   / \
  1   4
     / \
    3   6
→ False  (4 < 5 but 4 is the right child)

Solution

Approach - Recursive DFS with min/max bounds propagation.

BST validity is a global property, not a local one: a node must be greater than every ancestor it sits to the right of and less than every ancestor it sits to the left of. Checking only node.left.val < node.val misses violations that span multiple levels. The fix is to carry an allowed open interval (min_val, max_val) down the recursion. Each node must satisfy min_val < node.val < max_val; if it does not, return False immediately. When you descend left, the current node becomes the new upper bound (the left subtree must stay below it), so you pass max_val = root.val. When you descend right, the node becomes the new lower bound, so you pass min_val = root.val. The root starts with (-inf, +inf) since it has no ancestor constraints, and a None node returns True because an empty subtree trivially satisfies any interval.

Trace the invalid tree 5 -> (1, 4 -> (3, 6)). Node 4 is in the right subtree of root 5, so it inherits the bound min_val = 5. The check 5 < 4 fails, so it returns False - even though 4 is locally consistent with its own children 3 and 6. That cross-level catch is exactly what the local comparison would miss. The strict inequalities also reject duplicate values, and the and in the return short-circuits, so a violation in the left subtree skips the right entirely.

Edge cases - A None root returns True. A single node passes against the infinite bounds. Equal values fail because the comparison is strict (<=/>= trips the guard).

Complexity - O(n) time, O(h) space - each node is checked once and the recursion stack reaches the tree's height (O(log n) balanced, O(n) degenerate).