#113 Path Sum II
the problem
In plain words
Return every root-to-leaf path whose values add up to targetSum. Write each path as the list of its values from the root down to the leaf. The paths may come in any order.
in root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
out [[5,4,11,2],[5,8,4,5]]
in root = [1,2,3], targetSum = 5
out []
in root = [1,2], targetSum = 0
out []
- 0 ≤ number of nodes ≤ 5000
- -1000 ≤ Node.val ≤ 1000
- -1000 ≤ targetSum ≤ 1000
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTree DFS (top-down)
Path Sum plus a record of the path. Keep one list: add the node on the way down, remove it on the way back up (backtracking), and save a copy whenever a leaf hits the target.
solutions
From brute force to optimal
Each call builds its own list: the parent's path plus this node. No undo needed — but every node pays for a copy.
- path = new ArrayList<>(pathAbove); path.add(node.val).
- At a matching leaf, add path to the result.
- Recurse left and right with the new list.
Every node copies a path of up to h values: O(n log n) when balanced, O(n²) for a chain.
Each frame on the stack keeps its own copy: 1 + 2 + … + h values (not counting the answer).
class Solution { public List<List<Integer>> pathSum(TreeNode root, int targetSum) { List<List<Integer>> result = new ArrayList<>(); walk(root, targetSum, new ArrayList<>(), result); return result; } /** pathAbove is never changed: every call makes its own, longer copy. */ private void walk(TreeNode node, int remaining, List<Integer> pathAbove, List<List<Integer>> result) { if (node == null) return; List<Integer> path = new ArrayList<>(pathAbove); // O(h) copy at EVERY node path.add(node.val); remaining -= node.val; if (node.left == null && node.right == null && remaining == 0) result.add(path); walk(node.left, remaining, path, result); walk(node.right, remaining, path, result); }}One ArrayList travels with the recursion. Add before recursing, remove after; copy only at a matching leaf.
- null → return.
- path.add(node.val); remaining −= node.val.
- Leaf with remaining 0 → result.add(new ArrayList<>(path)).
- Else recurse left and right.
- path.remove(path.size() − 1) before returning.
O(1) work per node, plus an O(h) copy for each of the k saved paths. The answer itself can hold Θ(n²) values in the worst case, and no method beats the size of its output.
One path list and the recursion stack, not counting the answer.
class Solution { public List<List<Integer>> pathSum(TreeNode root, int targetSum) { List<List<Integer>> result = new ArrayList<>(); walk(root, targetSum, new ArrayList<>(), result); // ONE path list, shared by every call return result; } private void walk(TreeNode node, int remaining, List<Integer> path, List<List<Integer>> result) { if (node == null) return; path.add(node.val); // choose this node remaining -= node.val; if (node.left == null && node.right == null && remaining == 0) { result.add(new ArrayList<>(path)); // save a COPY: path keeps changing } else { walk(node.left, remaining, path, result); walk(node.right, remaining, path, result); } path.remove(path.size() - 1); // un-choose: remove by INDEX }}Dry run
in the room
How to say it in the interview
talk track
- Say it's Path Sum with a recorded path, and that you'll share one list and undo each add (backtracking).
- Point at the two Java details before they bite: save
new ArrayList<>(path), and remove by index withpath.remove(path.size() - 1). - Give the cost honestly: O(n) for the walk plus O(h) per saved path; the answer can be Θ(n²) values in the worst case.
traps
result.add(path)without a copy: every saved entry is the same list, and by the end it is empty.path.remove(node.val)on aList<Integer>callsremove(int index)— it removes by position, not by value, and can throw IndexOutOfBoundsException. Remove the last index.- Returning early after saving a match, before the remove: the node stays in the path and corrupts every later answer. Undo on every way out.
what they ask next
Follow-ups
Every root-to-leaf path, no target (LC 257)?
The same backtracking walk; at every leaf, join the path into a string like "1->2->5".
Can you avoid recursion?
Use an explicit stack of (node, sum) and a parent map. At a matching leaf, climb the parent links to rebuild the path, then reverse it.
before you submit
Edge cases to test
- No matching path → [] (an empty list, never null).
- Two different paths with equal values ([1,1,1], target 2) → both are listed.
- A node with one child is not a leaf: [1,2] with target 1 → [].
practise next
Similar problems
- #112Path SumEasyin Tree Recursion
- #78SubsetsMediumin Backtracking
- #437Path Sum IIIMediumin Tree Recursion