Recursive BST Property
What you'll learn: How the BST invariant applies recursively to every subtree within a binary search tree.
The Power of Recursive Structure
You already know that a Binary Search Tree has an invariant: for any node, all values in its left subtree are smaller, and all values in its right subtree are larger. But here's the crucial insight: this property doesn't just apply at the root—it must hold true at every single node throughout the entire tree.
Think of it like Russian nesting dolls. Each doll (subtree) must follow the same rule independently. If you pick any node in the tree and treat it as the root of its own mini-BST, that subtree must satisfy the BST invariant perfectly.
Why This Matters
Consider a tree with root value 50. Its left child is 30 and right child is 70. But what if 30's right child is 60? Even though 60 is greater than 30 (satisfying the local parent-child relationship), it violates the BST property because 60 should be in 50's right subtree, not its left!
The recursive property catches this: when we check if 30's subtree is valid, we must ensure all its descendants are less than 50 (the original root). Each subtree isn't just checked against its immediate parent—it inherits constraints from all ancestors.
Verification Approach
To validate a BST recursively:
- Check the current node satisfies its local invariant
- Recursively verify the left subtree is a valid BST (with appropriate upper bound)
- Recursively verify the right subtree is a valid BST (with appropriate lower bound)
If any subtree at any level fails, the entire tree is invalid.
Key Takeaway: The BST property is recursive—every subtree must independently satisfy the BST invariant, not just the root node.