Algorithms / Bst Invariants
Least You Need to Know: BST Invariants, Search Ranges, and Inorder Structure
Binary-search-tree reasoning is about global range constraints, not just comparing a node to its direct children. Inorder traversal is sorted precisely because every left subtree stays below the node and every right subtree stays above it.
Least you need to know
- Every key in a BST left subtree is less than the node key.
- Every key in a BST right subtree is greater than the node key.
- Validation needs range information, not just parent-child comparisons.
- Inorder traversal of a valid BST visits keys in sorted order.
- Search, insert, and delete all follow the same ordering invariant.
Key notation
- low < key < high — valid range constraint while descending
- inorder — left, node, right traversal order
- BST — binary search tree with ordered keys
Worked example
- Root
8allows values< 8on the left and> 8on the right. - If the right child of
8is12, then a descendant value6under that right subtree is invalid even if it is< 12. - That is why BST validation carries an interval, not just the parent value.
- Inorder traversal of
3, 5, 7, 8, 10, 12is sorted because the invariant holds globally.
Common mistakes
- Checking only each node against its parent misses deeper violations.
- Duplicate-handling rules vary by implementation; interview problems usually specify strict inequality.
- Students sometimes assume every balanced tree is automatically a BST.
How to recognize it
- The problem says search or insert follows left/right comparisons by key.
- You need to validate a tree using allowed value ranges.
- A sorted inorder traversal would solve or verify the structure.
Next recommended lesson
Continue through this topic with Least You Need to Know: Condensation DAGs and Component-Level Ordering.
Least You Need to Know: Condensation DAGs and Component-Level OrderingRelated lessons
Keep going with nearby lessons in the same topic.