This sub-variant is the base case of the whole pattern, so it is worth being explicit about why the shape is what it is.

1. 1

   What does dfs return? Name the type before writing anything. One number? A boolean? A pair? Ambiguity here is what produces functions that half-return two different quantities.

2. 2

   What is the value for null? It must be the identity element of the combining operation — 0 for a sum or a height, true for a universal claim, Integer.MIN_VALUE for an unclamped max. Ask what the empty subtree contributes.

3. 3

   Is the answer returned or recorded? For sub-variant A they are the same value, which is exactly what makes it the easy case. When they diverge you are in C.

4. 4

   Why the visit must be postorder. Both children's answers must already exist when the parent combines them, and postorder is the only order where both recursive calls have returned — the point established in Pattern 1 A.

Answer these three before typing: what does dfs return; what is the value for null; is the answer the return value or a recorded one. Every bug in this pattern is one of those three answered wrongly.

LC 110's sentinel is a real complexity fix, not a trick. Returning -1 for something below me is already unbalanced short-circuits every ancestor, giving O(n). Computing height inside an outer traversal instead is O(n log n) on balanced trees and O(n^2) on skewed ones.

LC 222 turns a property into an algorithm. Complete means equal left and right spine heights imply a perfect subtree, so its size is 2^h - 1 with no traversal at all. When they differ, exactly one of the two recursive calls descends — hence O(log^2 n).

Use long for sums. LC 129, 1339 and 437 all overflow int on deep or wide trees, silently. Take any modulus at the end, not during.

dfs returns the height, or -1 meaning already unbalanced. Watch how the -1 at node 2 stops all work above it.

Answer false. Row 4 is the point: once -1 appears, no ancestor does any further work and the right subtree is never explored at all. The naive version — a height() call inside an outer isBalanced() traversal — would recompute heights at every level instead, which is where the extra log n factor comes from.

• Say the three questions out loud, in order. Return type, null value, returned-or-recorded. The gate for this sub-variant is literally answering them for LC 104.
• The identity element is derived, not recalled. What does the empty subtree contribute to this combine? Sum: 0. Height: 0. Universal claim: true. Max with no floor: MIN_VALUE.
• A sentinel value is a legitimate return type. -1 in LC 110 is not a hack — it is a second channel in the return, and it buys a whole complexity class. Explain the O(n) versus O(n log n) difference unprompted.
• Watch for problems where the constraint is the algorithm. LC 222's complete is the entire solution. Reading a constraint as decoration rather than as a lever is a recurring way to miss the intended approach.

• ✗Wrong identity for null

  Symptom: off-by-one at every leaf, propagating up the whole tree.

  Prevention: Ask what the empty subtree contributes to this specific combine, and answer per state.

• ✗Recomputing height inside an outer traversal (LC 110)

  Symptom: O(n log n) on balanced trees, O(n^2) on skewed ones.

  Prevention: Use the -1 sentinel and a single pass.

• ✗int sums on LC 129, 1339 or 437

  Symptom: silent overflow on deep or wide trees.

  Prevention: Accumulate in long; apply any modulus only at the end.

• ✗Combining before both calls have returned

  Symptom: you are writing preorder and calling it an aggregate.

  Prevention: Aggregates are postorder. Both children must be known before the parent combines.

Almost all the correctness lives in the base case, which is why it is worth writing carefully once and reusing.

1. 1

   Both absent. a == b catches it. Two nulls are the same reference, so this is true — structurally identical empty subtrees.

2. 2

   Exactly one absent. If the previous test failed and either is null, the structures differ. false, immediately.

3. 3

   Both present. Compare the values. If they differ the trees differ; if they match, the answer depends entirely on the children.

4. 4

   The pairing rule. For same tree you pair left-with-left. For symmetric you pair left-with-right. Same function, same base case, one argument swapped — which is why LC 101 is not a new algorithm.

The distinction the gate asks for: the crossed pairing in LC 101 is a parameter, not a different algorithm. One function walks two trees; how you line up the children is the only thing that changes.

Merging returns a node instead of a boolean. LC 617 uses the same skeleton with the base cases returning the surviving subtree rather than true/false — the shape is identical, only the return type moves.

Subtree-of is this plus an outer search. LC 572 runs the two-tree comparison from every candidate root, which is why its cost is the product rather than the sum.

Watch the pairing column. Each call compares a node from the left subtree against its mirror in the right subtree.

Answer true. The only thing separating this from LC 100 is which children were paired at step 1: (a.left, b.right) and (a.right, b.left) instead of the straight pairing. Same base case, same recursion, one argument order.

• Write the base case once and reuse it. Three lines, and they cover every structural comparison in this sub-variant.
• a == b is deliberate, not lazy. It handles both-null in a single reference comparison. Worth pointing out, because it looks like a shortcut and is actually the precise test.
• Name the pairing before you write the recursion. Left with right or left with left. Stating it turns LC 101 from a puzzle into a one-argument change.
• The return type can be a node. Merging is the same walk with a different payload. Recognising that keeps LC 617 from feeling like a new problem.

• ✗Checking a == null && b == null then a == null || b == null separately

  Symptom: correct but verbose, and easy to get the order wrong.

  Prevention: a == b collapses the first case cleanly. Then a single || test.

• ✗Using the straight pairing for LC 101

  Symptom: you have written same tree and answered a different question.

  Prevention: Symmetric pairs left-with-right. State the pairing explicitly before recursing.

• ✗Comparing values before checking for null

  Symptom: NullPointerException on the first lopsided pair.

  Prevention: Base cases first, always: both-null, one-null, then values.

• ✗Assuming subtree-of is a single comparison

  Symptom: misses matches that start below the root.

  Prevention: LC 572 needs an outer walk over candidate roots as well.

One argument, and once it lands the whole sub-variant is obvious.

1. 1

   Two different questions at each node. What is the best path that passes through this node? and what is the best path ending at this node that my parent could extend? They have different answers.

2. 2

   The bend uses both sides. left + right goes down one child, through the node, and down the other. Every one of the node's connections is now spent.

3. 3

   So a parent cannot extend it. To reach the node from above, the parent needs the node's upward connection — which a bent path has already used. There is no way to attach.

4. 4

   Hence record one, return the other. Record left + right into a running best; return 1 + max(left, right), a path that has one side free and can therefore be continued.

Say it out loud before coding: record the bend, return the continuation. Returning the recorded value is the classic wrong answer — a parent cannot build a longer path out of a child's bent path, because a bent path already used both of the child's sides.

LC 124 is LC 543 plus one clamp. Math.max(0, child) encodes a branch with a negative total is simply not taken. Without it, a tree of all-negative values returns a sum of several of them instead of the single least-bad node.

The clamp belongs on the child's contribution, not on the result. Clamping the final answer would forbid a legitimately negative maximum on an all-negative tree; clamping the child is what expresses I may decline this branch.

The best path here bends at node 2, well below the root. Watch the two columns come apart.

The diameter is 3 edges — the path 4 - 2 - 1 - 3, recorded at the root in row 5. Row 3 is where the two columns first diverge: node 2 records a bend of 2 — the path 4 - 2 - 5, already finished — while returning 2 as a continuation, the path 4 - 2, which still has a free end pointing up. The root can extend the second and could never extend the first.

• This is the sub-variant that decides the pattern. The gate asks you to state the record/return distinction for LC 543 unprompted. Producing the code without the sentence is exactly what it is designed to catch.
• Name both quantities before writing the function. The bend and the continuation. Two names, two lines, and the bug becomes unwriteable.
• The clamp is a modelling decision. max(0, child) says I am allowed to decline this branch. Justify it on an all-negative tree and it stops being a magic zero.
• A running best is legitimate mutable state. Recording into a field while returning something else is not a hack — it is what makes one postorder pass sufficient.

• ✗Returning the recorded value

  Symptom: plausible but wrong on any tree where the best path bends below the root.

  Prevention: Say it before coding: record the bend, return the continuation.

• ✗Omitting Math.max(0, child) in LC 124

  Symptom: wrong on all-negative trees — it sums several negatives instead of taking the best single node.

  Prevention: A branch with a negative total is never taken. The clamp encodes that.

• ✗Clamping the recorded answer instead of the child

  Symptom: an all-negative tree wrongly reports 0.

  Prevention: Clamp the child's contribution. The answer itself may legitimately be negative.

• ✗Using one variable for both quantities

  Symptom: the two meanings collide and the bug is invisible on symmetric test trees.

  Prevention: Two names. The compiler cannot catch this one for you.

The distinction between D and E is one of the cleanest in the pattern, and the gate asks for it directly.

1. 1

   The state travels as a parameter. dfs(node, maxSoFar) — the value is on the call stack, one copy per frame, invisible to siblings.

2. 2

   Each child gets a freshly computed value. max(maxSoFar, node.val) produces a new value for the call. The parent's own variable is untouched.

3. 3

   So there is nothing shared to restore. When the call returns, the frame vanishes and with it the child's copy. No cleanup step exists because no mutation happened.

4. 4

   Contrast with E and F. There the state is a shared list or map. Every mutation on the way down needs an exact inverse on the way up, or one branch's data leaks into the next.

The distinction the gate asks for: sub-variant D needs no backtracking because the state is recomputed per child rather than mutated in a shared structure. E and F mutate, so they must undo.

The seed value is a small modelling choice. LC 1448 can start with root.val or with Integer.MIN_VALUE — both are correct, and one reads better. Being able to say why either works shows you understand what the parameter means.

Depth is the simplest inherited state of all, which is why the DFS form of LC 199 in Pattern 1 D is really this sub-variant wearing a traversal hat.

A node is good if no node on the path from the root to it is greater. Watch maxSoFar change per branch without any restoration.

Four good nodes. Notice rows 2 and 4: the left branch carried maxSoFar = 3 while the right branch carried 4, at the same time, with no interference. Neither branch had to restore anything — each simply received its own value. Hold that state in a shared field instead and the left branch's 3 would leak into the right.

• Name the direction before you write the signature. Does information flow up or down? Up means a return value; down means a parameter. Getting that right first eliminates most of the design.
• The no-undo property comes from immutability, not from luck. Passing a value creates a copy per frame. That single fact is the whole D-versus-E distinction.
• The counter can be a return value or a field. Summing the children's counts keeps the function pure, which is usually the cleaner choice and is worth preferring when it costs nothing.
• Depth-based problems are this sub-variant. Anything phrased as at depth d or on the path so far is inherited state, even when it is presented as a traversal problem.

• ✗Holding the inherited state in a shared field

  Symptom: one branch's value leaks into its sibling.

  Prevention: Pass it as a parameter. A fresh value per call is what makes the undo unnecessary.

• ✗Adding backtracking that is not needed

  Symptom: harmless but confusing, and it suggests the D/E distinction has not landed.

  Prevention: Nothing shared was mutated, so there is nothing to restore.

• ✗Choosing a seed that excludes the root

  Symptom: the root is misclassified, and every count is off by one.

  Prevention: Seed with root.val or Integer.MIN_VALUE, and be able to say why your choice includes the root.

• ✗Returning the state instead of the count

  Symptom: the function reports the running max rather than the answer.

  Prevention: The state goes down; the count comes up. Two different channels.

Three details, and each one corresponds to a specific wrong answer people actually produce.

1. 1

   The path is shared, so it must be restored. One list represents the current root path. Entering a node appends; leaving must remove. The undo goes after all recursive calls, on every exit path.

2. 2

   Recording must copy. The list keeps changing after you record it. Storing the reference means every result points at the same object, which is empty by the time the walk finishes.

3. 3

   A leaf is not a null. left == null && right == null is a leaf. n == null is the empty subtree one step beyond it — and recursing into both children of a leaf reaches it twice.

4. 4

   Which is why the tests are not interchangeable. Use n == null as the leaf condition and every root-to-leaf answer is counted twice, or half-paths get accepted, depending on where you put the record.

The two rules, stated as one: one undo per mutation, placed after all recursive calls on every exit path — and record new ArrayList<>(path), never the list itself.

The undo has to survive early returns. If any branch returns before the bottom of the function, that path also owes a removeLast. A try/finally, or simply having a single exit point, removes the whole class of bug.

LC 257 and 113 are the same walk with different payloads — a string versus a summed list. The discipline is identical, which is why they are graded as one skill.

Target 8. Follow the path column: it must return to exactly its previous contents each time a branch finishes.

Result [[5, 3]]. Rows 4 and 5 are the whole discipline: without them, row 6 would begin from [5, 4, 3] and produce [5, 4, 3, 3]. And had row 6 recorded path itself instead of a copy, the final answer would be an empty list — the walk empties it on the way out.

• Pair every mutation with its inverse as you type it. Write addLast and removeLast in the same keystroke burst, then fill the recursion between them. The bug then cannot be written.
• The copy is not defensive programming, it is correctness. The list is guaranteed to change afterwards. Recording a reference records a future empty list.
• State the leaf condition without hesitating. The gate says so explicitly. left == null && right == null — and know why n == null is a different, also-necessary test.
• Early returns owe an undo too. The most common leak is a branch that returns before reaching the bottom of the function.

• ✗addLast without a matching removeLast

  Symptom: paths from one branch leak into the next.

  Prevention: One undo per mutation, placed after all recursive calls, on every exit path.

• ✗Recording the path list instead of a copy

  Symptom: every result is the same list — and it ends up empty.

  Prevention: new ArrayList<>(path) at the moment of recording.

• ✗Treating n == null as the leaf condition

  Symptom: root-to-leaf answers counted twice, or half-paths accepted.

  Prevention: A leaf is left == null && right == null. Both tests exist and mean different things.

• ✗Putting the undo before the recursive calls

  Symptom: the children walk with an incomplete path.

  Prevention: The undo is the last statement, after both calls have returned.

One idea carried across, and two details that make the carry legitimate.

1. 1

   The array becomes the root path. In LC 560 the prefix sums come from a[0..i]. Here they come from the chain of ancestors down to the current node — which is exactly a contiguous sequence, so the same counting works.

2. 2

   The lookup is unchanged. answer += prefix[p - k] counts how many ancestors have a running sum that makes the segment between them and here equal k.

3. 3

   The seed. prefix.put(0L, 1) before the first call, so that a path starting at the root is counted. Seeding inside the DFS would re-seed at every node.

4. 4

   The undo. The path shrinks when you return, so the map must shrink with it. Decrementing prefix[p] is the last statement of the DFS body — otherwise a node's sum stays visible to its cousins.

The sentence that makes current root path true: the decrement is the last statement of the DFS body. Without it, cousins see each other's sums and you count paths that would have to jump sideways across the tree.

Use long for the running sum. LC 437's values and depths can overflow int silently, and the failure looks like an ordinary wrong answer rather than a crash.

The seed goes before the first call, not inside it. Seeding inside means every node re-registers a zero prefix, which inflates the count by exactly the number of nodes.

Watch the map contents. The entry added when entering a node is gone again by the time its sibling is visited.

Three paths: 5-3, 3-5 and the right-hand 5-3. Row 4 is the sub-variant in one line — the left branch's entries are removed before the right branch runs. Skip the decrement and row 5 would still see 8:1 and 13:1 from the left branch, counting a path that steps sideways from one child to the other, which no tree path can do.

• Lead with the transfer. This is LC 560 with the array replaced by the root path. The gate asks for exactly that sentence, and it makes the rest of the solution follow.
• The undo is what defines the data structure. The map claims to describe the current path. That claim is only true because of the decrement — so the decrement is part of the definition, not cleanup.
• Seed once, outside. {0: 1} before the walk begins. It is what lets a path that starts at the root be counted at all.
• Downward only. This counts paths that run straight down. A path that bends through a node is a different question and a different sub-variant.

• ✗Prefix map not decremented on the way up

  Symptom: overcounts paths that appear to span two branches.

  Prevention: The decrement is the last statement of the DFS body.

• ✗Prefix map missing the {0: 1} seed

  Symptom: misses every path that starts at the root.

  Prevention: Seed before the first call, not inside it.

• ✗Seeding inside the DFS

  Symptom: the count is inflated by roughly the number of nodes.

  Prevention: One seed, before the walk starts.

• ✗int running sums

  Symptom: silent overflow on deep or large-valued trees.

  Prevention: Accumulate in long.

Two of the three cases are obvious. The third is the whole problem.

1. 1

   The base. null returns null; a node equal to p or q returns itself. Nothing subtle yet.

2. 2

   Both sides non-null. One target was found somewhere left and the other somewhere right. No node below n can contain both, so n is the lowest node that does — return n.

3. 3

   Exactly one side non-null, reading (a). The LCA was already determined deeper in that subtree. Passing it up unchanged preserves it, because no ancestor can be lower.

4. 4

   Exactly one side non-null, reading (b). The value returned is one target, and the other lies beneath it. Then that target is itself the LCA — so passing it up is again correct. The code never distinguishes the two, and does not need to.

The step the gate asks you to defend: if only one side returns non-null, it is either the LCA found deeper or one target that is an ancestor of the other — and passing it up is correct in both readings.

This version assumes both targets exist. If they might not, you must return (found_p, found_q, node) or run a containment check first — a standard follow-up, and a place where it worked on LeetCode is not an answer.

Say the assumption out loud before you rely on it. Unstated, it is the difference between a correct solution and one that confidently returns a node when one target was never in the tree.

Targets p = 5 and q = 4, where 4 sits beneath 5. This is reading (b), the case people find hardest to justify.

Answer 5. Row 5 is reading (b) in action: node 5 is one of the targets and the other is beneath it, so 5 short-circuits and returns itself without ever looking at what came up from node 2. Row 6 then passes it along unchanged. At no point did the code decide which reading it was in.

• Defend the one-sided case unprompted. Both readings, in one sentence. That is exactly what the gate names, and it is the only part of this problem that is not mechanical.
• State the existence assumption. This assumes both targets are present. Saying it before being asked converts a hidden bug into a deliberate scope decision.
• The short-circuit at a target is deliberate. Returning immediately on n == p || n == q is what makes reading (b) work without extra logic.
• On a BST, do not use this. The ordering lets you walk down in O(h) with no recursion at all. Reaching for the general algorithm on a BST misses the point of the constraint.

• ✗Assuming both targets exist without saying so

  Symptom: wrong answer when one is absent — a node is returned that is not an ancestor of anything.

  Prevention: Say the assumption out loud; if it is unstated in the problem, return a found-flag pair.

• ✗Trying to distinguish the two one-sided readings

  Symptom: extra state, extra branches, and no change in behaviour.

  Prevention: Passing the value up is correct in both. That is the point.

• ✗Continuing to search below a found target

  Symptom: correct but wasteful, and it breaks the reading-(b) shortcut.

  Prevention: Return immediately when the node is a target.

• ✗Using this on a BST

  Symptom: O(n) where O(h) was available.

  Prevention: On a BST, compare values and walk down. See Pattern 3 A.

Two structural facts. The second is where the bug lives.

1. 1

   Preorder supplies identity. Its first element is the root of the current subtree. Consuming left to right hands you each subtree's root in exactly the order you need it.

2. 2

   Inorder supplies the split. Find the root's position in the inorder range; everything before it is the left subtree, everything after is the right. That gives both sizes.

3. 3

   The cursor must be shared. Building the left subtree consumes an unknown number of preorder entries, and the right subtree must start after all of them. A per-frame copy cannot know that, so it rebuilds from the wrong slice.

4. 4

   Postorder reverses the order of construction. Read from the right, postorder gives root, then right subtree, then left. So LC 106 must build the right subtree first — the one swap that separates it from LC 105.

The single difference between LC 105 and LC 106: postorder is consumed from the right, so the right subtree must be built first. Write them back to back and state that difference from memory.

A hash map from value to inorder index turns the lookup from O(n) into O(1), taking the whole construction from O(n^2) to O(n). Worth building unprompted, and worth saying why.

Mirroring is a silent failure. Build the left subtree first in LC 106 and you get a perfectly valid tree that is the mirror of the right answer — no exception, no crash.

preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]. The cursor advances once per node, across all frames.

Rebuilt correctly. Row 3 is the reason the cursor cannot be copied: node 20's frame relies on frames 1 and 2 having already consumed 3 and 9. Hand each frame its own copy and node 20 would read 9 instead, building a completely different tree with no error raised.

• Name what each traversal contributes. Preorder gives identity, inorder gives the split. One sentence that makes the algorithm obvious and explains why one traversal is not enough.
• Write 105 and 106 back to back, deliberately. The gate asks for exactly this, because the difference is one line and it will not stick otherwise.
• Build the index map without being asked. O(n) versus O(n^2), for three lines. Explaining the improvement is as valuable as making it.
• A mirrored tree throws no exception. That is what makes the LC 106 ordering bug dangerous — it produces a plausible tree, silently.

• ✗Copying the pre cursor into each frame

  Symptom: subtrees built from the wrong slice; the result is a different tree entirely.

  Prevention: The cursor is shared state: a field, or an int[1].

• ✗Building the left subtree first in LC 106

  Symptom: a mirrored tree, and no exception thrown.

  Prevention: Postorder is consumed from the right, so the right subtree is built first.

• ✗Scanning the inorder array for each root

  Symptom: O(n^2) on skewed input.

  Prevention: Precompute a value-to-index map once.

• ✗Assuming distinct values

  Symptom: the inorder lookup becomes ambiguous and the reconstruction is arbitrary.

  Prevention: Check the constraint. With duplicates, the pair of traversals is not uniquely decodable.

Three encodings, one of which works. The reasons the other two fail are the content here.

1. 1

   Preorder alone is ambiguous. 3, 9, 20 could be a left chain, a right chain, or a root with two children. Nothing says where a subtree ends.

2. 2

   Markers supply the boundaries. A # says this subtree is empty, which is exactly the missing information. Now every recursive call knows when to stop.

3. 3

   Preorder makes the reader's job deterministic. The next unread token is always the root of the next subtree, so decoding mirrors encoding exactly — read root, decode left, decode right.

4. 4

   Inorder cannot work even with markers. The root sits somewhere in the middle of its own encoding, and nothing identifies which token it is. Without knowing the root you cannot split, and without splitting you cannot recurse.

The claim the gate asks you to explain: the null markers are the structure. Preorder plus markers is uniquely decodable; preorder alone is not, and inorder is not even with markers, because it cannot locate the root.

Deserialization uses one shared cursor, exactly as construction did in sub-variant H, and for exactly the same reason: the left subtree consumes an unknown number of tokens.

Structural identity is serialization plus a map. LC 652 canonicalises every subtree to a string and counts them — a direct reuse, and a good sign the sub-variant has landed.

Delimiters matter more than they look. 1,2 and 12 must not collide, so separate tokens explicitly rather than concatenating digits.

Encoding is a plain preorder walk that emits # for null. Decoding reads the same tokens in the same order.

Encoded as 1,2,#,#,3,4,#,#,#. Row 5 is the marker earning its place: without that final # the decoder cannot tell whether node 3 has a right child, and the encoding would describe several different trees. Every # removes exactly one ambiguity.

• The markers are data, not padding. Saying the nulls are the structure is the whole insight, and it is what the gate is checking.
• Be able to reject inorder with a reason. It cannot locate the root. That is a sharper answer than it does not work, and it demonstrates you understand what decoding requires.
• The shared cursor recurs. Same mechanism as sub-variant H. Noticing the reuse is worth more than the individual problems.
• Canonical strings enable subtree comparison. Once a subtree has a unique encoding, are these equal and find duplicates both become map lookups.

• ✗Serialising preorder without null markers

  Symptom: the string describes many different trees; decoding is arbitrary.

  Prevention: The markers are the structure. Emit one per absent child.

• ✗Trying to use inorder

  Symptom: the decoder cannot find the root and the whole approach collapses.

  Prevention: Preorder puts the root first, which is what makes decoding deterministic.

• ✗Copying the cursor during deserialization

  Symptom: subtrees decoded from the wrong offset.

  Prevention: One shared cursor, exactly as in sub-variant H.

• ✗Concatenating values without a delimiter

  Symptom: 1,2 and 12 become indistinguishable.

  Prevention: Emit explicit separators between tokens.

One ordering rule, and two pointer disciplines that depend on it.

1. 1

   Mutation invalidates what the children saw. If you swap left and right before recursing, the recursive calls operate on subtrees that have already moved — and invert them a second time.

2. 2

   So the calls go first. Recurse into both children, let them finish restructuring themselves, and only then rewire the current node's pointers.

3. 3

   LC 114 splices rather than rebuilds. Put the left subtree between the node and its right subtree. The rightmost node of the left subtree is the one that inherits the old right chain — find it, attach, then clear left.

4. 4

   LC 117 reuses the previous level as its queue. Once a level is linked by next, walking it gives you every parent in order, so you can link the level below without any auxiliary structure. The dummy head means the first child of a level needs no special case.

The rule that covers all three problems: recurse, then rewire. Swapping before the calls inverts subtrees twice, and in some shapes the tree comes back apparently unchanged.

The dummy head is the same idiom as the linked-list one. It exists so that is this the first element? never needs asking — and reaching for it unprompted is a small, strong signal.

LC 114's O(1) version is worth having over the recursive one, because the whole point of the problem is the space constraint. The gate asks specifically for that version.

At each node with a left subtree: find the rightmost node of that left subtree, hand it the current right chain, then move the left subtree across.

Result 1 -> 2 -> 3 -> 4 -> 5 -> 6, all on right pointers with every left cleared. Row 1 is the splice: node 4 is the rightmost of node 1's left subtree, so it is the node that must inherit the old right chain starting at 5. Attach it anywhere else and the tail is lost.

• State the ordering rule before writing. Recurse, then rewire. It covers inverting, flattening and linking, and it is the only bug worth worrying about in the recursive forms.
• Double inversion can look like success. On symmetric trees, swapping before recursing returns the original tree unchanged — which passes a careless test.
• The rightmost node is the attachment point. In LC 114 it is the only node whose right is free, which is why it inherits the old chain.
• LC 117 needs no queue at all. The level I already linked is the queue for the next one. That reframing is what makes the O(1) space possible.

• ✗Swapping children before recursing in LC 226

  Symptom: double inversion — and in some shapes the tree comes back unchanged.

  Prevention: Recurse, then rewire.

• ✗Attaching the old right chain to the wrong node in LC 114

  Symptom: the tail is lost and the flattened list is truncated.

  Prevention: The rightmost node of the left subtree inherits it — that is the only node with a free right.

• ✗Forgetting to clear left after splicing

  Symptom: the result is not a right-only chain, so it fails the problem's definition.

  Prevention: node.left = null as part of every splice.

• ✗Handling the first child of a level as a special case in LC 117

  Symptom: branchy, error-prone code.

  Prevention: Use a dummy head; the special case disappears.

Three design decisions, in order. The code is short once they are settled and unwriteable before.

1. 1

   Name the states. What choice does a node make? LC 337: robbed or not. LC 968: uncovered, covered, or holding a camera. The state set must be small and exhaustive.

2. 2

   Name the transition. How does a parent's state depend on its children's? This is where the constraint lives — if I rob this node I cannot rob its children, a camera here covers my children and my parent.

3. 3

   Name the null value, per state. Ask what the empty subtree contributes to each state individually. In LC 968 an absent child needs no cover, so null must be state 1 — return 0 instead and every leaf gets a camera it does not need.

4. 4

   Postorder is forced. Children's tuples must exist before the parent combines them, and postorder is the only topological order a tree traversal gives you.

The design decision that fails silently: ask what the empty subtree contributes to each state individually. In LC 968 null must be 1 — an absent child needs no cover — otherwise every leaf gets a camera.

LC 979 counts flow, not nodes. The return value is a surplus and may be negative; |surplus| coins must cross the edge to the parent, in either direction. Counting nodes instead of edge traffic is the wrong model and produces a plausible wrong number.

**LC 968's greedy is *place the camera as late as possible*** — at the parent of an uncovered node, because a camera at the parent covers strictly more than one at the child. That argument is what makes the greedy correct rather than merely reasonable.

The root needs a final check. cameras + (cover(root) == 0 ? 1 : 0) — the root has no parent to cover it, so it can finish uncovered.

Each node returns {rob, skip}. A robbed node forces both children to be skipped; a skipped node lets each child take its own better option.

Answer max(7, 6) = 7. Row 5 shows why one number per node would not do: the root's rob value needs its children's skip entries specifically, not their best. Collapse the tuple to a single best-so-far and that information is gone.

• Design the three parts before writing any code. States, transition, null-per-state. The gate for LC 968 asks you to do exactly that from scratch, without recalling the code.
• The null value is per state, not per problem. Asking what does the empty subtree contribute to this state separately for each entry is what prevents the leaf off-by-one.
• Justify the greedy, do not assert it. A camera at the parent covers strictly more than one at the child is why placing late is optimal. Without that sentence the solution is a guess that happens to pass.
• Watch for surplus-style returns. LC 979's negative values confuse people because they expect counts. Naming it flow across an edge fixes the model immediately.
• The root often needs a post-check. It has no parent, so any state that relies on the parent to resolve must be handled explicitly after the recursion returns.

• ✗Wrong identity for null in a DP state

  Symptom: off-by-one at every leaf — LC 968 gives a camera to each one.

  Prevention: Ask what the empty subtree contributes to each state, individually.

• ✗Returning one number instead of a tuple

  Symptom: the parent cannot distinguish the child's options, so the constraint cannot be enforced.

  Prevention: One entry per state. The tuple is the whole technique.

• ✗Counting nodes rather than edge flow in LC 979

  Symptom: a plausible number that is not the answer.

  Prevention: The return value is a surplus; |surplus| coins cross the edge, in either direction.

• ✗Forgetting the root's final adjustment in LC 968

  Symptom: the root can end uncovered and the count is one short.

  Prevention: cameras + (cover(root) == 0 ? 1 : 0).

First the impossibility, then the four-line derivation the gate asks for.

1. 1

   Why one DFS fails. A node's answer depends on nodes both below and above it. A single postorder pass only ever knows about the subtree, so it can compute the root's answer and nothing else.

2. 2

   Pass 1 collects what is local. A postorder walk gives size[v] for every node, and accumulates ans[root], the sum of distances from the root.

3. 3

   Pass 2 moves the root by one edge. Going from parent p to child c: every node inside c's subtree is now one step closer, and every node outside it is one step further away.

4. 4

   Which is the identity. ans[c] = ans[p] - size[c] + (n - size[c]), and simplifying gives ans[c] = ans[p] + n - 2 * size[c]. A preorder pass propagates it to the whole tree in O(n).

Derive this on a blank page, and say what each term counts: ans[c] = ans[p] + n - 2 * size[c] — size[c] nodes came one step closer, the other n - size[c] moved one step further.

The direction of the passes is not interchangeable. Pass 1 must be postorder because sizes aggregate upward; pass 2 must be preorder because each child's answer is derived from its parent's.

If the derivation will not come, draw a five-node tree and move the root by hand. The gate says this explicitly — the obstacle is almost never the algebra.

A six-node tree, n = 6, rooted at 0 with ans[0] = 8. Watch the formula applied to each child in turn.

Answers [8, 12, 6, 10, 10, 10]. Row 2 is the interesting one: moving the root towards the bigger subtree lowers the total, because four nodes got closer and only two got further. Row 1 moves towards a leaf and the total rises for the mirror-image reason. The formula is just that trade, written down.

• The recognition is the hard part. Every node needs its own answer is the signature of rerooting. Spotting it before writing an O(n^2) solution is what the sub-variant is for.
• Derive the identity, never recall it. The gate asks for a blank-page derivation and for what each term counts. The second half is what shows it is understood.
• The pass directions are forced. Postorder up for sizes, preorder down for answers. Neither can be swapped, and saying why is a clean way to show you see the dependency structure.
• Drawing beats algebra when stuck. Five nodes, move the root by hand, count. The formula falls out and then stays.

• ✗One DFS for a every node needs its own answer problem

  Symptom: O(n^2) and a time-limit failure.

  Prevention: That is the signature of rerooting: two passes.

• ✗Getting the sign wrong in the identity

  Symptom: answers drift further from correct the deeper you go.

  Prevention: - size[c] for the subtree that came closer, + (n - size[c]) for everything else.

• ✗Running pass 2 in postorder

  Symptom: a child's answer is computed before its parent's exists.

  Prevention: Pass 2 is preorder — the parent's answer is the input to the child's.

• ✗Forgetting that size includes the node itself

  Symptom: off-by-one in every delta.

  Prevention: size[v] counts v plus all its descendants.