Stage 1 · Code
Linked Lists & Trees
Tree Drills
Mix-and-match tree patterns — DFS depth, BFS breadth, path validation, symmetry checks, and diameter computation in one workout.
How to Drill Trees
Tree problems look diverse but reduce to a handful of traversal strategies. The fastest way to get good: recognise whether the problem needs DFS (depth-first, stack or recursion) or BFS (level-order, queue), then decide what state to accumulate. Most interview trees are binary trees, so master those six traversal orders — preorder, inorder, postorder, level-order, and their reverse variants.
Before writing a single line, answer: 'What does this node need from its children?' If the answer is a single value (height, sum, bool), recursion is usually cleaner. If the answer involves comparing siblings or levels, BFS may win.
Patterns at a Glance
| Pattern | Strategy | When to Use |
|---|---|---|
| Maximum / Minimum Depth | DFS post-order; return 1 + max(left, right) or min | Any 'height' or 'depth' question |
| Path Sum / Root-to-leaf | DFS with running sum; subtract from target at each node | Constraint involves root-to-leaf accumulation |
| Symmetry / Same Tree | Dual DFS: compare left.left vs right.right mirror pairs | Two trees or mirror images |
| Diameter | DFS returns height; update global max for left+right at each node | Longest path through any node |
| LCA | DFS returns node when found in either subtree | Lowest shared ancestor of two nodes |
Problems
Key Points
- DFS by default — most tree problems yield to a clean recursive traversal.
- BFS for level-order — shortest path, level-averages, right-side view all prefer a queue.
- Global state — diameter, maxPathSum, tilt all use a closure variable updated during DFS.
- Null checks first — always handle the nil child case before accessing .Val.
- Mirror patterns — symmetric tree, same tree, and subtree checks all compare two nodes at once.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.