Validate a BST
Scenario
A developer writes a quick check for a tree node: `if node.left.val < node.val < node.right.val: return True`. Their unit tests pass on small trees, but corrupt data slips into production.
Why does checking immediate parent-child relationships fail to validate a Binary Search Tree?
Why it exists
Problem: Checking only local parent-child pairs (`left.val < node.val < right.val`) misses global ancestor constraint violations deeper in subtrees.
Naive approach: Comparing each node only to its immediate left and right child pointers.
Better idea: Pass down a valid numerical range `(low, high)` that tightens at every step down the tree. A node is valid iff `low < node.val < high`.
Mental model
Carry an allowed valid range window down the tree; going left lowers the upper bound, going right raises the lower bound.
Start at the root with range `(-inf, +inf)`. When recursing to `node.left`, the upper bound becomes `node.val` (range `(low, node.val)`). When recursing to `node.right`, the lower bound becomes `node.val` (range `(node.val, high)`). If any node breaks `low < node.val < high`, the entire tree is invalid.
Repeated decision: is this node's value inside its allowed (low, high) range?
Explanation
The Killer Misconception (The Local-Compare Trap):
A naive implementation checks only immediate children:
`if node.left and node.left.val >= node.val: return False`
`if node.right and node.right.val <= node.val: return False`
Why this is WRONG:
Consider a tree where node `1` (the root's LEFT child) has a right child of `6`:
5
/ \
1 7
\
6
At node `1`, right child `6` passes local check (`6 > 1`). At node `6`, local check passes. But `6 > 5`, violating the global BST invariant because 6 is in 5's LEFT subtree! Local checks miss this completely.
Correct Approach 1: Tightening Bounds Range
Pass `low` and `high` parameters down recursively:
- `validate(node, low, high)`:
- `if node is None: return True`
- `if not (low < node.val < high): return False`
- `return validate(node.left, low, node.val) and validate(node.right, node.val, high)`
Correct Approach 2: Strictly Increasing In-Order Traversal
Recall from `dfs-pre-in-post` that an in-order traversal of a valid BST MUST yield strictly ascending values. Maintain a `prev` pointer during in-order traversal; if `curr.val <= prev`, the tree is invalid.
Application - Minimum Absolute Difference in a BST:
Because an in-order traversal outputs values in sorted ascending order, the minimum numerical difference between ANY two nodes in a BST must occur between adjacent nodes in the in-order traversal sequence. Tracking `curr.val - prev.val` during an in-order traversal finds the global minimum absolute difference in O(n) time without needing all-pairs comparisons.
Key points
- Global Ancestor Constraint: Every node in a BST must satisfy constraints imposed by ALL of its ancestors, not just its immediate parent.
- Range Tightening Invariant: Going left sets high = node.val; going right sets low = node.val. The valid window shrinks monotonically.
- In-Order Monotonicity: An in-order traversal of a valid BST yields a strictly increasing sequence without duplicates.
Pattern: Bounded Recursion / In-Order Validation
Recognition cues:
- BST validity check
- inherited range constraints
- strictly increasing in-order sequence
Failure signals
- Problem asks to check if a binary tree is a valid Binary Search Tree.
- Problem asks to find the minimum absolute difference between any two nodes in a tree.
Engineering examples
Database Index Integrity Verification
Verify that a database index file on disk has not been corrupted by hardware or software crashes.
Running a range-bounded validation or in-order check verifies global index integrity in O(n) time.
Property-Based Testing of BST Libraries
Automatically test custom Red-Black tree insertion/deletion logic under randomized mutation operations.
Range-bounded validation acts as an invariant checker invoked after every mutation.
When not to use
- General binary tree without search ordering guarantees: If data is not structured as a BST, range bounds checking is inapplicable.
Common mistakes
- Checking only immediate children (Local-Compare Trap): Failing to pass ancestor bounds down allows nodes deep in a subtree to violate high-level ancestor constraints.
- Using integer minimum/maximum limits: Using fixed constants like `-2147483648` fails if tree nodes contain `INT_MIN`. Use nullable `None` or float `'-inf'` / `'inf'` for initial bounds.
- Allowing duplicates with `<=`: Standard BST definition requires strictly less/greater bounds (`low < node.val < high`). Using `<=` permits duplicate invalid tree structures.
Recall questions
- Why is comparing `node.left.val < node.val < node.right.val` insufficient to validate a BST?
- How do range bounds change when recursing to the left child of a node?
- What property does an in-order traversal of a valid BST possess?
Questions & answers
Validate Binary Search Tree: Given the root of a binary tree, determine if it is a valid BST.
Use helper recursion with range bounds `(low, high)` initialized to `(-inf, +inf)`. At each node check `low < node.val < high` and recurse with updated bounds.
Approach: Top-down DFS with tightening (low, high) boundary constraints.
Minimum Absolute Difference in BST: Find the minimum absolute difference between values of any two nodes in a BST.
Perform an in-order traversal. Keep track of the previous visited node value `prev`. The minimum difference will always occur between adjacent values in the in-order sequence.
Approach: In-order DFS traversal; compute min diff between adjacent elements in sorted order.
Interesting facts
- Validation using range bounds is top-down O(n), while validation using in-order traversal is also O(n) but can early-exit the moment `curr <= prev` is detected.
Continue learning
Previous: BST: insert & search
Previous: DFS: pre / in / post
Next: Lowest common ancestor
Related: BST: insert & search
Related: DFS: pre / in / post
Related: Lowest common ancestor