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.

Example 1:

Input: root = [10,5,14,2,7]
Output: True

    10
   /  \
  5    14
 / \
2   7
→ True

Example 2:

Input: root = [10,2,14,null,null,7,19]
Output: False

    10           ← valid BST? no
   /  \
  2    14
      /  \
     7    19
→ False  (7 < 10 but 7 sits in 10's right subtree)

Constraints:

• -1000 <= Node.val <= 1000

Solution Breakdown

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 10 -> (2, 14 -> (7, 19)). Node 14 is in the right subtree of root 10, so its left child 7 inherits the bound min_val = 10. The check 10 < 7 fails, so node 7 returns False - even though 14 is locally consistent with its own children 7 and 19. 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).