Synthesis: which pattern to use?
Five tree patterns covered. Time to train the reflex: read a tree problem and know which tool to reach for — with justification.
The section's decision tree
1. Does the answer COMBINE from the subtrees (height, sum, validate, invert)?
→ RECURSIVE DFS (base case None → solve left → solve right → combine)
2. Is the question per LEVEL (values of each level, side view, minimum depth)?
→ Level-order BFS (queue + level-size trick)
3. Is it a BST (left < node < right)?
├── search / LCA / insert → descend only one side: O(h)
└── "k-th smallest" / sorted → IN-ORDER traversal (ascending)
4. Do I need to REBUILD or SERIALIZE the tree?
→ preorder gives the root; empty markers make the string reconstructible
5. Is the problem about PREFIXES or a dictionary of words?
→ TRIE (per-character path; O(L) per operation)
And the reflex that holds for the whole section: think recursively. Define the base case, trust that the recursion solves the children, and focus on the combination. Most trees yield to that habit.
The complete map of the section
| Pattern | Key question | Time | Space |
|---|---|---|---|
| Recursive DFS | "combine the children's result" | O(n) | O(h) |
| Level-order BFS | "per level / minimum depth" | O(n) | O(width) |
| BST (search/LCA) | "left < node < right" | O(h) | O(h) |
| BST in-order | "k-th / sorted" | O(n) | O(h) |
| Construction/serialization | "rebuild without ambiguity" | O(n) | O(h) |
| Trie | "prefixes / dictionary" | O(L) per op. | O(total chars) |
Notice the recurring O(h): the height governs the recursion's space and the time of the BST search. Balanced → log n; degenerate → n. This is the section's deep dive into Big-O — whenever you say O(h), know what h means.
Section quiz
Statements you have not seen in the lessons. Identify the pattern and the why. 7+ correct: ready for the exam.
🧠 Section quiz: Trees
0/81. 'Sum all the tree's values.' Which pattern and what is the combination?
2. 'What is the MINIMUM depth (to the shallowest leaf)?' Why is BFS a great choice?
3. 'In a BST, find the in-order successor of a value.' Which property helps?
4. 'Check whether a tree is mirrored around its center (symmetric).' Which pattern?
5. 'Autocomplete: given many words, answer quickly whether a prefix exists.' Which structure?
6. 'Maximum path sum in the tree (it can turn at a node, negative values).' Why is it DFS done carefully?
7. Why do so many tree algorithms have O(h) space instead of O(n)?
8. What is the master idea that unites almost the whole Trees section?
Ready for the exam?
The Trees section's final exam has three brand-new problems — easy, medium and hard — with hidden cases. The hard one (maximum path sum) is recursive DFS with the subtlety of separating "what I return to the parent" from "the best answer I can form here". The five lessons cover everything you need.
Good luck on the exam! Go back to the section page and click "Final exam".