Verifying BST Invariant
What you'll learn: How to check whether a binary tree truly satisfies the BST property using range-based validation.
The Challenge
You've learned what makes a valid BST: every node's left subtree contains only smaller values, and its right subtree contains only larger values. But here's the catch — it's not enough to just check each node against its immediate children. A node might look correct locally but violate the BST property globally.
For example, imagine a node with value 10 has a left child of 5, which looks correct. But if that left child has a right child of 12, we've violated the BST invariant — that 12 should never appear in node 10's left subtree, even though it's not a direct child.
The Solution: Range-Based Validation
The key insight is that every node in a BST must fall within a valid range:
- The root can be any value (range: negative infinity to positive infinity)
- When you go left, the maximum allowed value becomes the parent's value
- When you go right, the minimum allowed value becomes the parent's value
Think of it like a narrowing tunnel: as you descend the tree, the acceptable range for each node becomes tighter and tighter based on all ancestors above it, not just the immediate parent.
How It Works
Start at the root with an unlimited range. For each node, verify it falls within its allowed range. Then recursively check:
- Left child with updated maximum (current node's value)
- Right child with updated minimum (current node's value)
If any node falls outside its valid range, the tree isn't a valid BST.
Key Takeaway: Verifying the BST invariant requires tracking valid ranges through recursion — each node must respect constraints from all ancestors, not just its parent.