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.
The 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
Tiny worked example
- Root `8` allows values `< 8` on the left and `> 8` on the right.
- If the right child of `8` is `12`, then a descendant value `6` under 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, 12` is 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 this kind of problem
- 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.