Tree Algorithms & Patterns
This section covers the essential tree algorithms that appear in interviews, competitive programming, and real systems. Each algorithm has its own dedicated post with detailed explanations, code, and interactive animations.
The Algorithms
Height of a Tree
The foundational bottom-up recursion. 1 + max(left, right). Understand this and you understand half of all tree problems.
Lowest Common Ancestor
Two approaches: BST split-point (O(h)) and general DFS split-detection (O(n)). Plus advanced preprocessing methods.
BST: O(h) · General: O(n) →Diameter of a Tree
Longest path between any two nodes. Piggybacks on height computation in a single DFS pass.
O(n) single pass →Serialize / Deserialize
Convert trees to strings and back. Preorder + null markers, BFS encoding, and alternative approaches.
O(n) both directions →Interview Patterns
5 core patterns that cover 90% of tree interview problems: bottom-up DFS, top-down DFS, BFS, construction, BST tricks.
Templates + cheat sheet →Complexity Summary
| Operation | BST (average) | BST (worst) | AVL / Balanced |
|---|---|---|---|
| Search | O(log n) | O(n) | O(log n) |
| Insert | O(log n) | O(n) | O(log n) |
| Delete | O(log n) | O(n) | O(log n) |
| Traversal | O(n) | O(n) | O(n) |
| Height | O(log n) expected | O(n) | O(log n) guaranteed |
| LCA | O(h) | O(n) | O(log n) |
| Diameter | O(n) | O(n) | O(n) |
Suggested Reading Order
- Height, learn the bottom-up recursion pattern
- LCA, BST ordering + general DFS split
- Diameter, builds directly on height
- Serialization, practical encoding/decoding
- Interview Patterns, tie it all together with templates