257 · Binary Tree Paths

The first problem where the accumulator is a mutable list: add before recursing, remove after. That removal is the whole sub-variant. Everything else here you already have from LC 112.

1 — The problem

Return every root-to-leaf path as a string, "1->2->5" style. The leaf test is unchanged from LC 112; what changes is that the path itself must be materialised, not just summarised into a number.

And that changes the sharing rules. Compare the two accumulators:

Problem	Accumulator	Passed	Undo needed?
129, 112, 1448	`int`	by value — every frame owns a copy	No. The caller's copy was never touched.
257, 113, 437	`List`, `StringBuilder`, `Map`	by reference — every frame shares one object	Yes. Whatever you added must come off before returning.

That is the rule in general: immutable state flowing down needs no backtracking; mutable shared state does. The remove is not a stylistic tidy-up — without it, a sibling inherits the previous branch's nodes and the output is nonsense.

2 — Add, recurse, remove

Watch the path strip. After the leaf 5 is recorded, the list shrinks back through 5, then 2, before 3 is appended — and each shrink is a line-8 remove, not something the language did for you.

Line 8 runs on every exit from the method — leaf or not, success or not. That symmetry is what makes it correct: the method's contract is "the list is exactly as you gave it to me when I return", and any path out that skips the remove breaks it.

2.1 The three ways to get the remove wrong

Mistake	Symptom
Forgetting it entirely	The list only grows. The first path is right, and every later one is prefixed with the whole earlier traversal — `"1->2->5->3"`.
`return` early at the leaf, before line 8	Leaves never pop themselves. Sibling paths carry a stale leaf. This is the subtle one, because the code looks like it has a remove.
`path.remove(nd.val)`	Two bugs at once: on a `List<Integer>` that overload removes by index, not value; and even `remove(Integer.valueOf(v))` removes the first occurrence, which is the wrong one when values repeat. Always remove by last index.

If the early return is tempting — and it is, because "found a leaf, done here" reads naturally — restructure so the recursion sits in an else. Then there is exactly one exit and the remove cannot be skipped.

2.2 The alternative: don't share

Backtracking exists to avoid copying. If the paths are short, or you want the code to be obviously correct, hand each child its own list and the whole problem evaporates:

Java 21Copy-per-branch — no backtracking, O(n·h) memory traffic.7 lines

void dfs(TreeNode nd, String path, List<String> out) {
    if (nd == null) return;
    path = path.isEmpty() ? "" + nd.val : path + "->" + nd.val;
    if (nd.left == null && nd.right == null) { out.add(path); return; }
    dfs(nd.left,  path, out);
    dfs(nd.right, path, out);
}

String is immutable, so this is the int case again — and the early return is now harmless, because there is nothing to undo. It is genuinely fine for LC 257. Learn the backtracking version anyway: at LC 437 the shared structure is a hash map and copying it per node is not an option.

3 — Complexity and edge cases

Time O(n · h) — O(n) nodes, and building each output string costs O(h). Space O(h) for the path plus the output itself.
Single node: one path, ["1"]. The join must not emit a leading or trailing ->.
Empty tree: an empty list. Guard at the entry, or let the nd == null check handle it — but note that with the early-return version, a null root must not append anything.
A node with one child is not a leaf and emits no path of its own. Same trap as LC 112, same fix.
Duplicate values are the reason to remove by index rather than by value.

4 — Reference implementation

Java 21Backtracking on a shared list, matching the visualizer.16 lines

public List<String> binaryTreePaths(TreeNode root) {
    List<String> out = new ArrayList<>();
    dfs(root, new ArrayList<>(), out);
    return out;
}

private void dfs(TreeNode nd, List<Integer> path, List<String> out) {
    if (nd == null) return;
    path.add(nd.val);                              // add before recursing
    if (nd.left == null && nd.right == null) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < path.size(); i++) {
            if (i > 0) sb.append("->");
            sb.append(path.get(i));
        }
        out.add(sb.toString());
    }
    dfs(nd.left,  path, out);
    dfs(nd.right, path, out);
    path.remove(path.size() - 1);              // remove after — the whole sub-variant
}

Note there is no else and no early return: the leaf branch records and then falls through to the two recursive calls, which immediately hit the null guard. One exit, one remove.