Four lines that the whole of Pattern 2 rests on. The last one is the reason this sub-variant comes first.

1. 1

   The invariant. dfs(node) completely visits the subtree rooted at node and touches nothing outside it. That containment is what lets you reason about one node at a time.

2. 2

   The stack is the path. The chain of active calls is exactly root -> node. Any problem about the path from the root needs no extra data structure — it is already on the stack.

3. 3

   The base case. null is the empty subtree, a perfectly legal input. So the guard belongs at the top of the callee: one check, one place.

4. 4

   Why postorder computes aggregates. At the moment a postorder visit runs, both dfs calls have returned, so both subtree answers already exist. In pre- and inorder at least one child is still unknown when the parent acts — so no aggregate is available to combine.

Three orders, one skeleton, one moved line: if you cannot state why postorder is the only order that can compute a subtree aggregate, stop here — the whole of Pattern 2 depends on it.

Recursive DFS tolerates a null root; BFS never does. The if (node == null) return; guard absorbs the empty tree for free, whereas a queue template dereferences root immediately and needs an explicit guard. Worth knowing as an asymmetry rather than memorising per template.

Space is O(h), which is O(n) on a degenerate tree. A linked-list-shaped tree will overflow the stack, and that is the honest answer when asked about the worst case.

The same five-node tree, traced once. Each row is a moment during the single walk; the three columns show which order would emit at that moment.

Preorder 1 2 4 5 3, inorder 4 2 5 1 3, postorder 4 5 2 3 1. Row 6 is the one to look at: node 2 is emitted in postorder only after both 4 and 5 are finished — which is precisely why a postorder visit can combine their answers and a preorder visit cannot.

• Say the postorder sentence before you are asked. Both recursive calls have returned, so both subtree answers exist. That single line is the A gate, and it is the foundation of every problem in Pattern 2.
• Guard the callee, always. One if (node == null) return; at the top. Guarding at the call site doubles the branching, and the duplicated logic is where base-case bugs hide once the function grows.
• The call stack is free state. Root-path problems need no auxiliary structure in recursive DFS. Recognising that is what makes sub-variants E and F of Pattern 2 feel natural later.
• Name the space honestly. O(h), degrading to O(n) on a degenerate tree. Saying O(log n) without the caveat assumes balance you were never promised.

• ✗Guarding the caller: if (n.left != null) dfs(n.left)

  Symptom: duplicated null logic, and missed base cases as the function grows.

  Prevention: Guard the callee: one if (node == null) return; at the top, always.

• ✗Trying to compute a subtree aggregate in preorder

  Symptom: the parent acts before its children are known, so the aggregate is wrong or incomplete.

  Prevention: Aggregates are postorder. If the parent needs the children's answers, the visit goes after both calls.

• ✗Assuming O(log n) stack space

  Symptom: stack overflow on a degenerate, list-shaped tree.

  Prevention: Space is O(h). Only a balanced tree makes that O(log n).

• ✗Rewriting the skeleton per order

  Symptom: three near-identical functions and three chances to introduce a bug.

  Prevention: One skeleton, one moved line. The orders differ by placement, nothing else.

The inorder machine is worth deriving once; the postorder one is worth knowing precisely what it does and does not give you.

1. 1

   The inorder invariant. The stack holds exactly those ancestors whose left subtree is finished and whose own value has not yet been emitted. Everything the loop does maintains that sentence.

2. 2

   The two halves of the loop. Descend left while pushing — you are deferring every node you pass. Then pop, emit (its left subtree is now provably done), and move to its right child, because that is the only debt left.

3. 3

   The postorder trick. Root-Right-Left, emitted front-first, reads as Left-Right-Root. Push left first so that right pops first, and use addFirst so the reversal happens without a second pass.

4. 4

   What the trick does not give you. It produces the correct sequence, but each node is processed before its children. If the visit has a side effect that must happen after both children — freeing, folding, releasing — the timing is wrong even though the list is right.

The caveat that makes reversed-preorder a list trick rather than a traversal: it yields the correct list, not the correct visit moments. If you must act on a node strictly after both children (freeing, folding), use the lastVisited form.

LC 173's next() is amortized O(1), and the gate asks why. Each node is pushed exactly once and popped exactly once across the whole iteration, so n calls do O(n) total work even though a single call may descend a long left spine. Space is O(h).

Deque is both a stack and a queue, which is the hazard. push/pop give LIFO, add/poll give FIFO. Mixing them inside one method silently turns a BFS into a DFS.

Watch the stack. At every emit, the invariant holds: everything on the stack is an ancestor whose left subtree is finished and whose value is still owed.

Inorder 4 2 5 1 3, matching the recursive walk exactly. Note step 3: node 2 is emitted the moment it is popped, and only then does its right subtree get explored — which is the iterative restatement of the visit sits between the two calls.

• State the stack invariant, not the loop. Ancestors whose left subtree is done and whose value is still owed. The gate asks for it, and it reconstructs the code if you blank.
• The amortization argument is short. Each node is pushed once and popped once, so n calls cost O(n) overall. That is the whole answer to why is next() amortized O(1)?
• Know the postorder caveat before you use the trick. Right list, wrong moments. Volunteering that distinction shows you understand what a traversal order actually is.
• An iterator is a paused traversal. Framing LC 173 that way — rather than as a new problem — is what makes it a two-minute problem instead of a twenty-minute one.

• ✗Using reversed-preorder postorder for side effects

  Symptom: a node is processed before its children are done, so folds and frees happen in the wrong order.

  Prevention: It produces the right list, not the right timing. Use recursion or the lastVisited form.

• ✗Mixing push/pop with add/poll on one Deque

  Symptom: a silent DFS where you intended a BFS, or vice versa.

  Prevention: add/poll for FIFO, push/pop for LIFO. Never mix them in one method.

• ✗Pushing right before left in the postorder trick

  Symptom: the reversal comes out as the wrong order entirely.

  Prevention: Push left first so right pops first — that ordering is what the reversal depends on.

• ✗Emitting during the descend loop

  Symptom: you get preorder while believing you wrote inorder.

  Prevention: The descend loop only pushes. Emission happens after the pop.

The skeleton is four lines and one of them carries the whole idea. The second half of this section is the classic wrong recursion that BFS fixes outright.

1. 1

   The queue holds one frontier. At the top of the outer loop, everything in the queue is at the same depth. That is the property being maintained.

2. 2

   Draining while enqueueing breaks it. Each poll removes a node of the current level and each add appends a node of the next one, so q.size() changes meaning mid-loop.

3. 3

   The snapshot freezes the boundary. int sz = q.size(); captures the level's width before any of it is consumed, so the inner loop runs exactly over this level and stops.

4. 4

   The null-root guard. BFS dereferences root immediately by enqueuing it. Recursive DFS absorbs a null root in its base case; BFS must check explicitly.

The one line: int sz = q.size(); taken before the inner loop, never inside its condition. Without it the queue grows while you drain it and every level boundary is lost.

LC 111 is the trap that makes this sub-variant matter. The recursion everyone writes first — return 1 + Math.min(depth(left), depth(right)); — is wrong on every one-child node, because the absent child returns 0 and wins the min. A leaf is no children, not one null child, so the one-child case has to be handled explicitly.

BFS is strictly better for minimum depth. It returns at the first leaf it meets instead of exploring the entire tree, and it makes the one-child trap impossible to write.

The sz column is the whole lesson: it is read once per level, and the queue is longer than sz by the time the inner loop ends.

Result [[1], [2,3], [4,5]]. Look at row 2: sz was 2, but by the time the inner loop finished the queue held 2 more nodes. Had the condition read i < q.size(), the loop would have kept going straight into level three and produced [[1], [2,3,4,5]].

• The snapshot is the sub-variant. Every level-order derivative in D is this skeleton plus an accumulator. Getting the snapshot reflexive pays for eight problems.
• Know the null-root asymmetry. DFS templates tolerate it, BFS templates do not. It is a one-line fix and a guaranteed null-pointer exception if you forget it.
• For shallowest-anything, BFS beats recursion on merit. Not just stylistically — it terminates at the first hit rather than exploring the whole tree, and it sidesteps the one-child trap by construction.
• Space is O(w), not O(h). The widest level dominates. On a complete tree that is n/2, which is worth saying when comparing against DFS's O(h).

• ✗BFS without the q.size() snapshot

  Symptom: levels merge into one flat list.

  Prevention: Take int sz = q.size(); before the inner loop, never inside its condition.

• ✗1 + min(left, right) for minimum depth

  Symptom: wrong on every one-child node — the absent child returns 0 and wins the min.

  Prevention: A leaf is both children null. Handle the one-child case explicitly, or use BFS and avoid it.

• ✗Missing the null-root guard

  Symptom: NullPointerException on the first q.add(root) dereference.

  Prevention: Recursive DFS tolerates a null root; BFS never does. Guard explicitly.

• ✗Using Deque as a queue with push

  Symptom: silent DFS instead of BFS — the output looks plausible and is wrong.

  Prevention: add/poll for FIFO. push/pop is LIFO and belongs in sub-variant B.

One derivative that is better as a DFS, and one that punishes the obvious implementation. Together they are the whole sub-variant.

1. 1

   The skeleton does not change. Sub-variant C's loop, with the snapshot, is still underneath. Only the accumulator differs.

2. 2

   199 as a DFS. Visit right before left and record a node whenever depth == out.size(). The first node reached at any new depth is therefore the rightmost one, and the space cost is O(h) rather than O(w).

3. 3

   Zigzag's tempting mistake. Reversing the frontier looks like it produces alternating output, and it does — for one level.

4. 4

   Why it then breaks. Reversing the queue also reverses the order in which those nodes enqueue their children, so every level below inherits a scrambled ordering. The output is correct at level one and corrupt underneath.

The rule that keeps zigzag correct below level one: the direction flag belongs to the output list, never to the queue. Reverse the output; leave the frontier alone.

The 199 space trade-off is the gate. BFS costs O(w) — up to n/2 on a complete tree. The right-first DFS costs O(h). Being able to write both and say which is which is what is being tested.

LinkedList gives you addFirst for free, which is why zigzag needs no explicit reversal pass — you simply choose which end to append to.

The queue is drained left-to-right on every level. Only the side you append to changes.

Result [[1], [3,2], [4,5]]. The queue order never changed — nodes 2 and 3 still enqueued their children in the normal order, which is why level three comes out as [4, 5] and not reversed. Flip the queue instead and level three would have been corrupted by level two's reversal.

• Know both forms of 199 and their costs. O(w) BFS versus O(h) right-first DFS. The gate asks for both, and the space comparison is the point of asking.
• depth == out.size() is a neat first-arrival test. It works because the output list is built strictly in depth order — worth recognising, since the same idiom reappears in other first-arrival problems.
• Reverse the output, never the frontier. One sentence that prevents the only real bug in this sub-variant.
• Most derivatives are one line. Largest per level, average per level, last per level — all the same skeleton. Recognising that keeps four problems from feeling like four problems.

• ✗Implementing zigzag by reversing the queue

  Symptom: level one is correct and everything below it is corrupt.

  Prevention: Reverse the output list. The frontier's order determines the next level's enqueue order.

• ✗Visiting left before right in the DFS form of 199

  Symptom: you record the leftmost node at each depth — the left side view.

  Prevention: Right before left. That ordering is the entire trick.

• ✗Recording with depth > out.size()

  Symptom: off-by-one; depths get skipped or duplicated.

  Prevention: depth == out.size() is exactly first arrival at a new depth.

• ✗Using BFS reflexively when O(h) is available

  Symptom: O(w) space where O(h) would do — up to n/2 versus log n on a balanced tree.

  Prevention: Ask which dimension you are paying for before choosing the traversal.

Each problem here is easy once the coordinate is chosen and quietly wrong if the trap is missed.

1. 1

   Heap indexing. Assign the root index 0, then left = 2i and right = 2i + 1. This is the same numbering an array-backed heap uses, and it encodes horizontal position exactly.

2. 2

   Width is a difference, not a count. Under that numbering the width of a level is last - first + 1. Counting nodes instead undercounts every sparse level, because the gaps between the ends are part of the width.

3. 3

   Normalisation is mandatory. Raw indices double each level, so a deep alternating tree overflows — first int, then even long. Subtract the level's first index as you go, and carry the index as long.

4. 4

   LC 987's third sort key. Sorting by (col, row) alone leaves ties among nodes at the same position, and no traversal resolves them for you. The tiebreak is the node's value, and it has to be added explicitly.

One trap per problem: width is an index difference, so normalise against each level's first index and carry indices as long. And in LC 987 the third sort key is the node's value — nothing gives it to you for free.

Traversal order is not output order in LC 987. You collect (col, row, val) triples during any traversal you like, then sort. Trying to emit in the right order during the walk is the hard way to do it and usually wrong.

Normalisation also keeps the numbers readable while debugging, which matters more than it sounds when you are hand-tracing a deep tree.

A deliberately sparse tree. Watch level three: two nodes, width four.

Answer 4. Level three holds only two nodes, but they sit at normalised indices 0 and 3 — the two absent positions between them are genuinely part of the width. Count nodes instead of subtracting indices and you report 2, which is the single most common wrong answer to this problem.

• Choose the coordinate first, then the traversal. BFS or DFS both work once every node carries an index. Deciding the numbering is the real modelling step.
• Say why normalisation is needed, not just that it is. Indices double per level, so depth 60 overflows long. Subtracting the level's first index keeps them small permanently.
• The third sort key is a genuine interview trap. The gate names it specifically. Two nodes can share a column and a row, and only the value separates them.
• Gaps are data. Width counts the empty positions between the ends is the sentence that makes LC 662 obvious and its absence that makes it confusing.

• ✗Counting nodes per level as the width

  Symptom: undercounts every sparse level.

  Prevention: Width is lastIndex - firstIndex + 1 under heap indexing.

• ✗Heap indices without per-level normalisation

  Symptom: overflow, then negative widths as the numbers wrap.

  Prevention: Subtract the level's first index; carry indices as long.

• ✗Sorting LC 987 by (col, row) only

  Symptom: wrong order among nodes sharing a position.

  Prevention: The third sort key is the node's value. No traversal supplies it.

• ✗Trying to emit vertical order during the walk

  Symptom: a complicated traversal that is still in the wrong order.

  Prevention: Collect triples, then sort. Traversal order is not output order.

Two claims. The first tells you to change tools; the second stops the new tool from hanging.

1. 1

   Downward-only recursion cannot reach the answer. From the target node, a node k steps away may be a sibling, an ancestor, or in a completely different branch. A top-down DFS has no route to any of them — it is not a matter of being slow, it is a matter of being unable.

2. 2

   A parent map makes the structure undirected. Record every node's parent once, and each node now has up to three neighbours: left, right, parent. Distance in the tree becomes ordinary graph distance.

3. 3

   Which means cycles. An undirected edge between a node and its parent is traversable both ways — a 2-cycle. BFS on a cyclic graph without a visited set bounces between them forever.

4. 4

   Build the map before you start. Populating it lazily during the BFS misses ancestors above the target, because you only discover parents for nodes you have already reached from above.

Say this before writing code — the gate calls it the most transferable in the pattern: parent map + BFS + visited. The visited set is mandatory, not an optimisation: parent links create 2-cycles, so BFS without it never terminates.

At depth k, the entire frontier is the answer. You do not filter — BFS has already grouped the nodes by distance, so the whole queue at that moment is the result.

seen.add(nb) doubles as the enqueue condition. Java's Set.add returns false if the element was already present, so one call both tests and marks — which is why the loop body stays a single line.

Target is node 5, k = 2. Watch the frontier move upward at step 1 — which is precisely what a downward DFS could never do.

Answer [1]. Node 1 is two steps away only by going up from 5 to 3 and then down — there is no downward path from 5 to 1 at all. Notice also step 2: node 3's neighbour list includes 5, which is already seen; without the visited set the search would walk straight back down and oscillate forever.

• The recognition is the skill, not the code. Distance in any direction means parent map plus BFS plus visited. Saying that before writing anything is exactly what the gate tests.
• Name why visited is mandatory. Not for efficiency — for termination. Parent links create 2-cycles and the BFS would never stop.
• Build the parent map eagerly. One complete DFS first. Lazy population is a subtle bug that only shows up on targets deep in the tree.
• The frontier is the answer. BFS groups by distance for free, so no filtering pass is needed at depth k.
• This generalises past trees. Once you see a tree is a graph with extra promises, problems about infection spread, nearest leaf and time-to-reach all become the same BFS.

• ✗Graph BFS on a tree without visited

  Symptom: infinite loop between a node and its parent.

  Prevention: Parent links create 2-cycles. Use seen.add(nb) as the enqueue condition.

• ✗Building the parent map lazily during the BFS

  Symptom: missing ancestors above the target.

  Prevention: The parent map must be complete before the BFS starts.

• ✗Trying to solve it with a downward DFS

  Symptom: you can reach descendants and nothing else.

  Prevention: The question is undirected. Change the structure, not the traversal.

• ✗Filtering the frontier at depth k

  Symptom: unnecessary work, and a chance to filter wrongly.

  Prevention: Everything in the queue at depth k is exactly k away. Return the lot.

Morris is short and every line is load-bearing. The proof that the tree survives is the part you will actually be asked for.

1. 1

   No stack means the tree must remember. Recursion and an explicit stack both store the return path outside the tree. With O(1) space neither is available, so the path has to live in the structure.

2. 2

   The predecessor has a free pointer. The rightmost node of cur's left subtree is the node visited immediately before cur in inorder, and its right is null by definition of being rightmost. That null is the slot to borrow.

3. 3

   First visit: thread and descend. pred.right = cur records where to return, then go left. You will come back up through that thread automatically.

4. 4

   Second visit: undo, emit, continue. Arriving with pred.right == cur proves the left subtree is finished. Set pred.right = null first, restoring the tree, then emit cur and move right.

The invariant an interviewer will ask you to prove: every thread created is destroyed before its node is emitted, so the tree is bit-identical when the loop exits.

Total work is still O(n): each edge is walked at most twice, once to build a thread and once to find it again. Say amortized O(n), constant space and be ready to justify the factor of two.

The loop condition needs both terms. pred.right != null alone spins forever on the second visit, because the thread you created is exactly what makes pred.right non-null. The second term pred.right != cur is what recognises your own breadcrumb.

2 with children 1 and 3. Two visits to the root: one to thread, one to undo and emit.

Inorder 1 2 3, and the tree is back exactly as it started — 1.right was set at step 1 and cleared at step 3, before node 2 was emitted. Step 2 is the pretty part: moving to cur.right from node 1 follows the borrowed thread and climbs back up without any stack at all.

• The undo is the answer, not the threading. Anyone can create a thread. The gate is prove the tree is unmodified at the end, which is entirely about where the undo sits.
• Justify the factor of two, do not hide it. Each edge is walked at most twice — once building a thread, once finding it. Amortized O(n), constant space is the precise claim.
• Both terms of the loop condition earn their place. One detects the end of the subtree, the other detects your own breadcrumb. Dropping either hangs the traversal.
• Know when Morris is inappropriate. It mutates the tree transiently. Under concurrent access, or when mutation is forbidden outright, it is the wrong answer even though it is the clever one.

• ✗Morris without removing the thread

  Symptom: the returned tree is corrupt, and a second traversal loops forever.

  Prevention: The else branch must set pred.right = null before emitting.

• ✗Loop condition with only pred.right != null

  Symptom: infinite loop on the second visit — your own thread satisfies the condition.

  Prevention: Both terms: pred.right != null && pred.right != cur.

• ✗Emitting before undoing

  Symptom: the invariant thread destroyed before emit breaks, and the proof you are asked for is false.

  Prevention: Undo, then emit, then move right — in that order.

• ✗Claiming plain O(n) without the caveat

  Symptom: an imprecise complexity claim on a question specifically about cost.

  Prevention: Each edge is walked up to twice; say amortized.

Three steps of nothing changes, then the one step that does.

1. 1

   The child list replaces the two fields. node.left and node.right were only ever a fixed-size collection of children. A list is the same thing without the arity restriction.

2. 2

   The loop replaces the two calls. for (Node c : node.children) dfs(c); is exactly the two recursive calls, generalised. Pre- and postorder still mean before the loop and after the loop.

3. 3

   BFS needs no change at all. Enqueue every child instead of two. The size snapshot from sub-variant C is untouched, so level-order and its derivatives generalise for free.

4. 4

   The identity element does change. A fold over an empty list must return something, and that value is the base case. It is the only decision the binary form let you avoid making.

The only genuinely new decision: the identity element for max over zero children is 0, not -infinity and not 1. Get that wrong and every leaf reports the wrong depth.

Pick the identity by asking what the fold should return for nothing. Sum of no numbers is 0; max of no depths is 0 because depth is non-negative; min of no values is +infinity. Stating it that way makes it a derivation rather than a memory test.

Ordering-sensitive logic does not generalise. Anything phrased as left before right — the DFS form of LC 199, inorder itself — has no meaning once children are an unordered list.

Root with three children, one of which has two children of its own. The fold at each node is max over children, then + 1.

Depth 3. Rows 1, 2, 3 and 5 are all the identity doing its job: a leaf's loop never executes, best stays 0, and the node returns 1. Initialise best to -infinity instead and every one of those rows returns garbage that then poisons the fold above it.

• Derive the identity, do not recall it. What should this fold return for no children? Sum: 0. Max of a non-negative quantity: 0. Min: +infinity. The gate asks you to state it.
• The generalisation is genuinely free for A through D. Saying so — and meaning it — is the point of this sub-variant. It is not a new technique, it is the same ones with the arity restriction lifted.
• Watch for logic that assumed two children. Anything that says left or right by name is not generalisable, and that is worth noticing before you start rather than after.
• Null children still need guarding. A child list can contain nulls depending on the problem's representation. The callee guard from sub-variant A still applies.

• ✗Initialising the fold to -infinity for a depth

  Symptom: every leaf returns nonsense, which propagates up the whole tree.

  Prevention: The identity for max over zero children is 0. A leaf is depth 1.

• ✗Initialising to 1

  Symptom: every depth comes out one too large.

  Prevention: The + 1 for the node itself happens once, at the return. The identity is the children's contribution, which is 0.

• ✗Generalising order-sensitive logic

  Symptom: left-versus-right reasoning has no meaning over a list.

  Prevention: Check whether the binary version depended on ordering before porting it.

• ✗Rewriting BFS for n-ary

  Symptom: wasted effort, and a fresh chance to drop the size snapshot.

  Prevention: Enqueue all children instead of two. Nothing else about sub-variant C changes.