Trees, BSTs and Tries
Know the traversal orders cold, reason about BST invariants over whole subtrees rather than single edges, and know why balanced and high-fan-out trees exist.
Key points
- 1
Pre-order is node-left-right, in-order is left-node-right (sorted for a BST), post-order is left-right-node, and level order uses a queue.
- 2
A BST requires every key in a left subtree to be smaller than the node, not just the left child. Validate with (low, high) bounds or an in-order scan.
- 3
Plain BSTs degrade to O(n) on sorted input. AVL trees keep height under about 1.44 log₂ n; red-black trees allow up to 2 log₂(n + 1) but rotate less.
- 4
Many tree problems are one post-order pass that returns a value up and updates a global best: diameter, balance checking, maximum path sum.
- 5
Pre-order plus in-order identifies a tree uniquely; pre-order plus post-order does not when a node has a single child.
- 6
Tries give O(m) prefix queries, and segment and Fenwick trees give O(log n) range queries with point updates.
- 7
Databases use B+ trees because high fan-out minimises page reads and linked leaves make range scans sequential.
Common traps
Checking only a node and its direct children accepts invalid BSTs.
The diameter path doesn't have to pass through the root.
A path-sum check that succeeds at a non-leaf node is wrong for root-to-leaf problems.
Read the source
Test yourself on Trees, BSTs and Tries
Ten questions, with the answer and explanation after each one.