Builds on Top-Down DFS, which you haven’t finished yet.
Root-to-Leaf Path Backtracking
Path Sum II (LC 113)(opens leetcode.com)
You're given the root of a binary tree and a target number targetSum. Collect every root-to-leaf path whose node values add up to targetSum, with each path reported as a plain list of values (not node objects).
A root-to-leaf path always starts at the root and ends at a leaf — a node with no children at all.
Root-to-Leaf Paths
Choose ➔ Explore ➔ Un-choose| 1 | from typing import Optional |
| 2 | |
| 3 | class TreeNode: |
| 4 | def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None): |
| 5 | self.val = val |
| 6 | self.left = left |
| 7 | self.right = right |
| 8 | |
| 9 | def path_sum(root: Optional[TreeNode], target: int) -> list[list[int]]: |
| 10 | """Path Sum II: every root-to-leaf path whose values add up to target. |
| 11 | Time: O(N * H) (copying each found path) | Space: O(H) path + recursion stack |
| 12 | """ |
| 13 | results: list[list[int]] = [] |
| 14 | path: list[int] = [] # One shared buffer, grown and shrunk symmetrically |
| 15 | |
| 16 | def dfs(node: Optional[TreeNode], rem: int) -> None: |
| 17 | if not node: |
| 18 | return |
| 19 | path.append(node.val) # 1. CHOOSE |
| 20 | if not node.left and not node.right and rem == node.val: |
| 21 | results.append(list(path)) # 📸 SNAPSHOT a copy at a valid leaf |
| 22 | dfs(node.left, rem - node.val) # 2. EXPLORE both children |
| 23 | dfs(node.right, rem - node.val) |
| 24 | path.pop() # 3. UN-CHOOSE (restore state on return) |
| 25 | |
| 26 | dfs(root, target) |
| 27 | return results |
path holds exactly the values from the root down to the current node, and rem is target minus the sum of the values above the current node.One shared path list always holds exactly the nodes from the root to the current node, because every append on the way in has a matching pop on the way out. At a leaf whose value equals the remaining sum rem, save list(path), a copy, since the shared list keeps changing after you return. Pop after both children, even when the node matched; an early return before pop() leaves a stale value in every later path.
See it run
Root-to-leaf paths with one shared path list, step by step
node nonerem -results []
Each circle is a tree node. The path row shows the shared list, with its end on the right. The results row holds the copies.
nodethe node being entered or lefton patha node whose value is in the shared path listcopiedthe nodes whose values were copied into results
Call dfs on the root 5 with rem = 22. path is empty.
Gotcha 1 of 4
- The trap
Gotcha 1: Returning early before
path.pop()runsMistakeif not node.left and not node.right and rem == node.val: results.append(list(path)) returnFixif not node.left and not node.right and rem == node.val: results.append(list(path))What happens: Every
path.appendneeds a matchingpath.pop(). An earlyreturnafter a match skips that pop. The leaf's value then stays inpath. Each laterpopthen removes the value one level too high. In the example, the second answer starts[5, 4, 8]instead of[5, 8].Example: Path Sum II (LC 113): root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22Mistake: returns [[5, 4, 11, 2], [5, 4, 8, 4, 5]]Fix: returns [[5, 4, 11, 2], [5, 8, 4, 5]]
- You only need a yes/no or a count, as in Path Sum (LC 112), not the list of nodes on each matching path. See Top-Down DFS
- The choices come from a flat list and any group of picked items is an answer, as in Subsets (LC 78), not one path from the root to a leaf. See Subsets
Deep Dive
Why path always holds the route from the root to the current node
path is one list that all calls share. The blueprint changes it in a fixed pattern. A call to dfs(node, rem) does path.append(node.val) first. It then calls dfs on both children. It does path.pop() last, after both children return.
Each call adds one value and removes the same value before it returns. So when a call returns, path is the same as it was when the call started. While a call runs, path holds the values of the nodes from the root to that node, and nothing else. rem is target minus the sum of the values above the node, so at a leaf, rem == node.val means the whole path adds up to target.
Example: Path Sum II (LC 113) with root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1] and targetSum = 22. The walk makes 10 appends and 10 pops. The leaf 7 has rem = 2, so it is not saved. The leaf 2 has rem = 2, so [5, 4, 11, 2] is saved. The leaf 13 is not saved, the leaf 5 saves [5, 8, 4, 5], and the leaf 1 is not saved. The result is [[5, 4, 11, 2], [5, 8, 4, 5]].
The trap: the saved path must be a copy
results.append(path) stores the list itself, not its values. The walk keeps changing that list. At the end every pop has run, so path is empty. Every saved item is the same empty list. On the example above, the function returns [[], []] and not [[5, 4, 11, 2], [5, 8, 4, 5]].
results.append(list(path)) makes a new list with the current values. Later changes to path do not touch it. A copy of a path of length L costs O(L).
The trap: pop() must run after a match too
A match is a good result, so it is tempting to write return right after the save. The return skips path.pop(). The value of the leaf stays in path.
Every later pop then removes the value one level too high. On the example, the second answer is [5, 4, 8, 4, 5] and not [5, 8, 4, 5]. The 4 from the first branch was never removed.
The same two lines of the blueprint prevent both faults. Save with list(path), then let the code fall through to the two recursive calls and to path.pop(). Do not return early.
One more fault is to save on rem == node.val without the leaf test. For root = [1, 2] and targetSum = 1, the node 1 has rem == 1, but it is not a leaf. The correct result is []. The leaf test not node.left and not node.right is part of the match.
The cost, and the neighbour cards
Each node is entered once, with one append and one pop, so the walk is O(N). The extra cost is the copies. Each saved path costs O(H), where H is the height of the tree, so the total is O(N * H) in the worst case. The space is O(H) for path and for the recursion stack, not counting the saved results.
Example: the walk above saves 2 paths of 4 values each, so the copies cost 8 value moves in total.
Path Sum (LC 112) is the neighbour card. It only asks for yes or no, so a value passed down is enough and there is no path. Subsets (LC 78) also appends, recurses and pops, but its choices come from a flat list and every group of choices is an answer. Here the choices follow the edges of a tree and only a root-to-leaf path is an answer.
Binary Tree Paths (LC 257) saves every path as text. Smallest String Starting From Leaf (LC 988) reads path backward, from the leaf up to the root.
60-Second Pitch
"I need every root-to-leaf path with a given sum, so I use depth-first search with one shared list path. At each node I append its value, call both children with rem - node.val, and pop the value. Every append has a matching pop, so path always holds the route from the root to the current node. At a leaf where rem equals the leaf value, I save list(path), a copy, because the shared list keeps changing. I never return before the pop. The walk is O(N) and the copies make the worst case O(N * H). The space is O(H)."
Common Questions
- Why do you save
list(path)and notpath? pathis one list that all calls share.results.append(path)stores that same list. By the end, everypophas run, so the list is empty, and every saved path shows as[].list(path)makes a new list with the values at that moment.- What is the time complexity of Path Sum II (LC 113)?
The walk is
O(N), because each node is entered once. Each saved path is copied, and a copy costs up to O(H), where H is the height of the tree. So the worst case is O(N * H). The space is O(H) forpathand the recursion, not counting the output.- Why must the pop run even after a match?
Each append needs one pop. If a match returns early, its pop is skipped and the leaf's value stays in
path. Then every later pop removes a value one level too high. On the example the second answer would be[5, 4, 8, 4, 5].- How is it different from Path Sum (LC 112)?
Path Sum only needs yes or no. A number passed down,
rem, is enough, and nopathexists. Path Sum II needs the nodes of each matching path, so it also keepspathwith an append before the calls and a pop after them, and it copies at a leaf.- Could you pass a new list down and avoid
pop()? Yes. Call
dfs(node.left, rem - node.val, path + [node.val]). Each call has its own list, so there is nothing to undo and nothing to copy again. The cost is that every call builds a list of length up to H, so each node costs O(H). It is simpler and slower than one shared list.
SWE Reasoning
Spot it
- The task asks for the paths themselves, not only for a count or a yes or no: "return all root-to-leaf paths".
- Each path ends at a leaf, and a path is checked against a target such as a sum.
- The wording says "root-to-leaf", "paths" or "every route".
- The state of a path is a list that can grow by one value and shrink by one value.
- The answer is a list of lists, so every saved path must be a separate copy.
The invariant, step by step
pathstarts empty anddfs(root, target)is called.dfs(node, rem)starts withpath.append(node.val). Nowpathholds the values from the root tonode.remistargetminus the sum of the values abovenode. At a leaf,rem == node.valmeans the whole path adds up totarget.- At such a leaf,
results.append(list(path))saves a copy, becausepathwill change again. - The call passes
rem - node.valto both children. Each child call appends and removes its own value, sopathis the same when the child returns. path.pop()removesnode.val. Nowpathholds the values from the root to the parent, which is what the parent expects.
Traps
results.append(path). It saves the shared list. At the end it is empty. Savelist(path).returnright after a match. It skipspath.pop(), and a stale value stays in every later path. Let the code reach the pop.- No leaf test. A node in the middle of the tree can match the sum, but its path does not end at a leaf. Test
not node.left and not node.right. - Pop placed before the recursive calls. The children then see a
pathwithout this node. - Reading
pathin the wrong direction.pathgoes from the root down. If the answer is read from the leaf up, reverse it.
Practice
Builds on Top-Down DFS, which you haven’t finished yet.
Root-to-Leaf Path Backtracking
Path Sum II (LC 113)(opens leetcode.com)
You're given the root of a binary tree and a target number targetSum. Collect every root-to-leaf path whose node values add up to targetSum, with each path reported as a plain list of values (not node objects).
A root-to-leaf path always starts at the root and ends at a leaf — a node with no children at all.
Root-to-Leaf Paths
Choose ➔ Explore ➔ Un-choose| 1 | from typing import Optional |
| 2 | |
| 3 | class TreeNode: |
| 4 | def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None): |
| 5 | self.val = val |
| 6 | self.left = left |
| 7 | self.right = right |
| 8 | |
| 9 | def path_sum(root: Optional[TreeNode], target: int) -> list[list[int]]: |
| 10 | """Path Sum II: every root-to-leaf path whose values add up to target. |
| 11 | Time: O(N * H) (copying each found path) | Space: O(H) path + recursion stack |
| 12 | """ |
| 13 | results: list[list[int]] = [] |
| 14 | path: list[int] = [] # One shared buffer, grown and shrunk symmetrically |
| 15 | |
| 16 | def dfs(node: Optional[TreeNode], rem: int) -> None: |
| 17 | if not node: |
| 18 | return |
| 19 | path.append(node.val) # 1. CHOOSE |
| 20 | if not node.left and not node.right and rem == node.val: |
| 21 | results.append(list(path)) # 📸 SNAPSHOT a copy at a valid leaf |
| 22 | dfs(node.left, rem - node.val) # 2. EXPLORE both children |
| 23 | dfs(node.right, rem - node.val) |
| 24 | path.pop() # 3. UN-CHOOSE (restore state on return) |
| 25 | |
| 26 | dfs(root, target) |
| 27 | return results |
path holds exactly the values from the root down to the current node, and rem is target minus the sum of the values above the current node.One shared path list always holds exactly the nodes from the root to the current node, because every append on the way in has a matching pop on the way out. At a leaf whose value equals the remaining sum rem, save list(path), a copy, since the shared list keeps changing after you return. Pop after both children, even when the node matched; an early return before pop() leaves a stale value in every later path.
See it run
Root-to-leaf paths with one shared path list, step by step
node nonerem -results []
Each circle is a tree node. The path row shows the shared list, with its end on the right. The results row holds the copies.
nodethe node being entered or lefton patha node whose value is in the shared path listcopiedthe nodes whose values were copied into results
Call dfs on the root 5 with rem = 22. path is empty.
Gotcha 1 of 4
- The trap
Gotcha 1: Returning early before
path.pop()runsMistakeif not node.left and not node.right and rem == node.val: results.append(list(path)) returnFixif not node.left and not node.right and rem == node.val: results.append(list(path))What happens: Every
path.appendneeds a matchingpath.pop(). An earlyreturnafter a match skips that pop. The leaf's value then stays inpath. Each laterpopthen removes the value one level too high. In the example, the second answer starts[5, 4, 8]instead of[5, 8].Example: Path Sum II (LC 113): root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22Mistake: returns [[5, 4, 11, 2], [5, 4, 8, 4, 5]]Fix: returns [[5, 4, 11, 2], [5, 8, 4, 5]]
- You only need a yes/no or a count, as in Path Sum (LC 112), not the list of nodes on each matching path. See Top-Down DFS
- The choices come from a flat list and any group of picked items is an answer, as in Subsets (LC 78), not one path from the root to a leaf. See Subsets
Deep Dive
Why path always holds the route from the root to the current node
path is one list that all calls share. The blueprint changes it in a fixed pattern. A call to dfs(node, rem) does path.append(node.val) first. It then calls dfs on both children. It does path.pop() last, after both children return.
Each call adds one value and removes the same value before it returns. So when a call returns, path is the same as it was when the call started. While a call runs, path holds the values of the nodes from the root to that node, and nothing else. rem is target minus the sum of the values above the node, so at a leaf, rem == node.val means the whole path adds up to target.
Example: Path Sum II (LC 113) with root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1] and targetSum = 22. The walk makes 10 appends and 10 pops. The leaf 7 has rem = 2, so it is not saved. The leaf 2 has rem = 2, so [5, 4, 11, 2] is saved. The leaf 13 is not saved, the leaf 5 saves [5, 8, 4, 5], and the leaf 1 is not saved. The result is [[5, 4, 11, 2], [5, 8, 4, 5]].
The trap: the saved path must be a copy
results.append(path) stores the list itself, not its values. The walk keeps changing that list. At the end every pop has run, so path is empty. Every saved item is the same empty list. On the example above, the function returns [[], []] and not [[5, 4, 11, 2], [5, 8, 4, 5]].
results.append(list(path)) makes a new list with the current values. Later changes to path do not touch it. A copy of a path of length L costs O(L).
The trap: pop() must run after a match too
A match is a good result, so it is tempting to write return right after the save. The return skips path.pop(). The value of the leaf stays in path.
Every later pop then removes the value one level too high. On the example, the second answer is [5, 4, 8, 4, 5] and not [5, 8, 4, 5]. The 4 from the first branch was never removed.
The same two lines of the blueprint prevent both faults. Save with list(path), then let the code fall through to the two recursive calls and to path.pop(). Do not return early.
One more fault is to save on rem == node.val without the leaf test. For root = [1, 2] and targetSum = 1, the node 1 has rem == 1, but it is not a leaf. The correct result is []. The leaf test not node.left and not node.right is part of the match.
The cost, and the neighbour cards
Each node is entered once, with one append and one pop, so the walk is O(N). The extra cost is the copies. Each saved path costs O(H), where H is the height of the tree, so the total is O(N * H) in the worst case. The space is O(H) for path and for the recursion stack, not counting the saved results.
Example: the walk above saves 2 paths of 4 values each, so the copies cost 8 value moves in total.
Path Sum (LC 112) is the neighbour card. It only asks for yes or no, so a value passed down is enough and there is no path. Subsets (LC 78) also appends, recurses and pops, but its choices come from a flat list and every group of choices is an answer. Here the choices follow the edges of a tree and only a root-to-leaf path is an answer.
Binary Tree Paths (LC 257) saves every path as text. Smallest String Starting From Leaf (LC 988) reads path backward, from the leaf up to the root.
60-Second Pitch
"I need every root-to-leaf path with a given sum, so I use depth-first search with one shared list path. At each node I append its value, call both children with rem - node.val, and pop the value. Every append has a matching pop, so path always holds the route from the root to the current node. At a leaf where rem equals the leaf value, I save list(path), a copy, because the shared list keeps changing. I never return before the pop. The walk is O(N) and the copies make the worst case O(N * H). The space is O(H)."
Common Questions
- Why do you save
list(path)and notpath? pathis one list that all calls share.results.append(path)stores that same list. By the end, everypophas run, so the list is empty, and every saved path shows as[].list(path)makes a new list with the values at that moment.- What is the time complexity of Path Sum II (LC 113)?
The walk is
O(N), because each node is entered once. Each saved path is copied, and a copy costs up to O(H), where H is the height of the tree. So the worst case is O(N * H). The space is O(H) forpathand the recursion, not counting the output.- Why must the pop run even after a match?
Each append needs one pop. If a match returns early, its pop is skipped and the leaf's value stays in
path. Then every later pop removes a value one level too high. On the example the second answer would be[5, 4, 8, 4, 5].- How is it different from Path Sum (LC 112)?
Path Sum only needs yes or no. A number passed down,
rem, is enough, and nopathexists. Path Sum II needs the nodes of each matching path, so it also keepspathwith an append before the calls and a pop after them, and it copies at a leaf.- Could you pass a new list down and avoid
pop()? Yes. Call
dfs(node.left, rem - node.val, path + [node.val]). Each call has its own list, so there is nothing to undo and nothing to copy again. The cost is that every call builds a list of length up to H, so each node costs O(H). It is simpler and slower than one shared list.
SWE Reasoning
Spot it
- The task asks for the paths themselves, not only for a count or a yes or no: "return all root-to-leaf paths".
- Each path ends at a leaf, and a path is checked against a target such as a sum.
- The wording says "root-to-leaf", "paths" or "every route".
- The state of a path is a list that can grow by one value and shrink by one value.
- The answer is a list of lists, so every saved path must be a separate copy.
The invariant, step by step
pathstarts empty anddfs(root, target)is called.dfs(node, rem)starts withpath.append(node.val). Nowpathholds the values from the root tonode.remistargetminus the sum of the values abovenode. At a leaf,rem == node.valmeans the whole path adds up totarget.- At such a leaf,
results.append(list(path))saves a copy, becausepathwill change again. - The call passes
rem - node.valto both children. Each child call appends and removes its own value, sopathis the same when the child returns. path.pop()removesnode.val. Nowpathholds the values from the root to the parent, which is what the parent expects.
Traps
results.append(path). It saves the shared list. At the end it is empty. Savelist(path).returnright after a match. It skipspath.pop(), and a stale value stays in every later path. Let the code reach the pop.- No leaf test. A node in the middle of the tree can match the sum, but its path does not end at a leaf. Test
not node.left and not node.right. - Pop placed before the recursive calls. The children then see a
pathwithout this node. - Reading
pathin the wrong direction.pathgoes from the root down. If the answer is read from the leaf up, reverse it.