Module Review: Trees
You’ve moved from linear lists to hierarchical power.
1. Key Takeaways
- Structure: Recursive definition (Node + Left + Right).
- BST: Sorted property enables O(log N) search.
- Traversal:
- DFS: Stack (Recursion). Pre/In/Post.
- BFS: Queue. Level Order.
- LCA: The meeting point of two nodes.
2. Cheat Sheet
| Algorithm | Time Complexity | Space Complexity | Use Case |
|---|---|---|---|
| DFS (Pre/In/Post) | O(N) | O(H) | Exhaustive search, Serializing. |
| BFS (Level Order) | O(N) | O(W) (Width) | Shortest Path (Unweighted), Layer-by-layer. |
| BST Search | O(log N) / O(N) | O(H) | Database Indexing, Sets. |
| LCA | O(N) | O(H) | Genealogy, Routing. |
3. Interactive Flashcards
What traversal yields sorted order in a BST?
Inorder Traversal (Left → Root → Right).
What data structure is used for BFS?
Queue.
What is the worst-case height of a BST?
O(N) (Skewed / Linked List). Balanced is O(log N).
Where is the Lowest Common Ancestor logic derived from?
Postorder Traversal (Bottom-Up).