Validating BST Property
You'll learn how to programmatically verify whether a binary tree actually satisfies the BST invariant.
The Core Idea
Just because a tree looks like it might be a BST doesn't mean it is. The BST property requires that every node's value falls within a valid range determined by its ancestors. For each node, all values in its left subtree must be less than the node's value, and all values in its right subtree must be greater than the node's value.
The naive mistake? Only checking immediate children. A node might have correct children but still violate the BST property if a deeper descendant breaks the rules inherited from ancestors higher up.
The Range-Based Approach
Think of each node as having a "permitted range"—a minimum and maximum value it must stay between. As you traverse:
- Left child: inherits the parent's minimum, but its maximum becomes the parent's value
- Right child: inherits the parent's maximum, but its minimum becomes the parent's value
Start at the root with range (-∞, +∞). Recursively check that:
- The current node's value is within its range
- Its left subtree satisfies the BST property with the updated range
- Its right subtree satisfies the BST property with the updated range
If any node violates its range constraint, the entire tree fails validation.
When to Use This
Use this validation when you need to verify that a binary tree someone else created (or you imported) actually follows BST rules. It's also useful after complex tree manipulations to ensure correctness.
Key Takeaway: Validating the BST property requires checking that every node falls within the valid range imposed by all its ancestors, not just comparing immediate parent-child relationships.