Trees show up far less in production code than in interviews — but the recursion shape they teach is general. The pattern: define what a node returns to its parent; let recursion handle the structure.
The recursion template
For any tree problem, ask three questions:
- What’s the base case? Almost always
Nonereturns the identity (0, empty, sentinel). - What does each child compute? Recurse on left and right.
- What does this node return / update? This is the only interesting line.
A node-local computation often does double duty: it returns one value to its parent, and updates a global maximum (closure variable, self.best) for “diameter” / “max path sum” type questions.
BST invariants worth memorizing
- In-order traversal is sorted.
kth smallestis “stop afterkin-order visits.” Use a stack, not full traversal. - Search / insert / delete is
O(log n)on balanced,O(n)on degenerate. Plain BSTs degrade to lists on sorted input. Production trees are always self-balancing (red-black, AVL, B-tree). - Validation is not “left.val < root.val < right.val”. That fails for grandchildren. Pass
(min, max)bounds down.
DFS vs BFS, decided
- DFS (recursion or explicit stack): natural for path / subtree questions, “does any path satisfy P,” tree construction from traversals.
- BFS (queue): natural for level-order, “shortest path in unweighted graph,” “min steps to reach state.”
- Multi-source BFS (push all sources upfront, then standard BFS): rotting oranges, walls and gates, anything where multiple starting points expand simultaneously. Often misidentified as DP.
The deciding question: does the answer care about depth/level? BFS. Otherwise DFS.
Construction from traversals
preorder + inorder or postorder + inorder uniquely determine a binary tree. The recursion: preorder[0] is the root; find it in inorder to split left/right subtrees. Naive O(n²); index inorder into a hash for O(n).
preorder + postorder does NOT uniquely determine the tree.
Tries
A trie is just a tree where each edge is a character. Useful when:
- You need prefix queries at scale (“autocomplete,” “longest common prefix in set”).
- The dataset has heavy prefix overlap; the trie compresses better than
nindependent strings.
Not useful when prefix isn’t the access pattern — for “is this string in the set,” a hash set wins on memory and constants.
What you actually use in production
Trees in code: rare. Trees in indexes: everywhere — B-trees in databases, log-structured merge trees in LSM databases (RocksDB, Cassandra), Merkle trees in version control and content addressing. Knowing the patterns helps you read the implementations, not write them.