BST Range Property
You'll learn how to generalize the BST invariant so that every node's key must fall within a valid range determined by its ancestors.
The Core Idea
You already know the basic BST invariant: left children are smaller, right children are larger. But here's the deeper insight: every node in a BST must satisfy range constraints inherited from all ancestors above it, not just its immediate parent.
When you go left from a node, you've set an upper bound for all descendants in that subtree. When you go right, you've set a lower bound. These constraints accumulate as you travel down the tree.
How Range Constraints Accumulate
Consider a root with key 50. Everything in the tree must be valid, but:
- If you go left to
30, all nodes in that subtree must be< 50 - If from
30you go right to40, that node must satisfy both< 50(from root) and> 30(from parent) - So
40lives in the valid range(30, 50)
Think of it like descending through narrowing hallways: each decision point makes your available space smaller.
Why This Matters
This range property is crucial for:
- Validating whether a binary tree is actually a BST
- Understanding why simply checking parent-child pairs isn't enough
- Implementing correct insertion and search operations
For example, this tree violates BST properties even though each parent-child pair looks okay locally:
20
/ \
10 30
/
25 ← Invalid! Must be > 20 AND < 30 ✓, but what about > 10? Not checked!
Key Takeaway: Every node in a BST must respect a valid range (min, max) inherited from all ancestors along its path from the root, not just its immediate parent.