DSA sheet · Trees · DFS pattern

Path Sum II

Path Sum (Problem 15) only asked whether a good root-to-leaf path exists. Path Sum II asks for all of them, written out as lists of values. To write a path out, we have to remember the nodes we walked through. Walking back up the tree means we must also forget them again. That "remember on the way down, forget on the way back up" step is called backtracking, and it is the real lesson of this video. The teacher finds the need for it during her dry run, so we will too.

Every problem below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Path Sum II with DFS + backtracking
• Part B · Backtracking up close: the two bugs to avoid
• Part C · Revision page

Part 0 · Before starting

From Path Sum (Problem 15), the teacher says it's a must-know

• Leaf = a node with no left and no right child. A root-to-leaf path starts at the root and ends exactly at a leaf.
• We carry the target down and subtract each node's value for its children ("shrinking target").
• At a leaf, the path is good when target == leaf.val.

One Python fact you need for backtracking

When you pass a list into a function, Python does not copy it. The function gets the very same list. If any call appends to it or pops from it, every call sees the change, because there is only one list.

def add_seven(lst):
    lst.append(7)

path = [5, 4]
add_seven(path)
print(path)          # [5, 4, 7]  the caller's list changed too

saved = path         # NOT a copy, just a second name for the same list
path.pop()
print(saved)         # [5, 4]     saved changed as well!

snapshot = list(path)   # a real copy (path[:] also works)
path.pop()
print(snapshot)      # [5, 4]     the copy is safe
print(path)          # [5]

Keep this in mind. Both bugs in Part B come from this one fact.

Part A · Path Sum II with DFS + backtracking

LeetCode 113

1The question in simple words

Given the root of a binary tree and targetSum, return every root-to-leaf path whose values add up to targetSum. Each path is a list of node values from root to leaf. The answer is a list of lists.

             5
            / \
           4   8
          /   / \
        11   13  4
        / \     / \
       7   2   5   1          targetSum = 22

This tree has 5 root-to-leaf paths (one per leaf):

Answer: [[5, 4, 11, 2], [5, 8, 4, 5]]. If no path works, return an empty list [].

2What the constraints tell us

• Nodes: 0 to 5000 → the tree can be empty. DFS needs its base case anyway, since the recursion always runs into None children. (A BFS version would need a special check for the empty tree.)
• Values: −1000 to 1000, and we add them along a path, so think about overflow. The teacher's argument: a path takes one node from each level, and a balanced tree with 5000 nodes has only about 12–13 levels. So a path sum stays small, around 13 × 1000.
• n = 5000 is small enough that a linear-time solution is clearly the fastest you can hope for, and it passes easily.

3Intuition: a trail of footprints

Imagine walking down the tree and leaving a footprint on each node you step on. Your footprints, read from the top, are your current path.

• Going down to a node: add a footprint (append its value to path).
• At a leaf with the right sum: take a photo of your footprints and put it in the answer album (save a copy of path).
• Going back up from a node, because you're done with it: rub out that node's footprint (pop it from path). Otherwise, when you walk down another branch, the old footprints would still be there and the path would be wrong.

That last step is backtracking: undo your own change before you return, so the caller finds things exactly as they were.

4Building the logic from the example

The teacher builds the code in small steps. She writes what she understands first, then dry-runs it, and lets the dry run show her what's missing.

Step 1: we need an outer list and an inner list

• The outer list ans collects all the good paths. It is made once, outside the recursive function, and the main function returns it at the end.
• The inner list path holds the nodes of the path we're on right now. So the DFS function needs three things: the node, the target still needed, and the path.

Step 2: base case → just return

If the node is None, there's nothing to add and nothing to check. Return. Here the function doesn't give back True/False. It fills ans as it goes, so a plain return is enough.

Step 3: step onto the node → add it to the path

After the None check, put the node's value into path. At 5 with an empty path, path becomes [5].

Step 4: at a leaf, check the target

The teacher reminds us of the two ways from Path Sum. Running sum: 5, then 9, then 20, then 27 at 7 or 22 at 2, compared with the target at each leaf. Shrinking target: 22 → 17 → 13 → 2, and at the leaf compare what's left with the leaf's value. She uses the shrinking target.

Why check only at a leaf? Because a path has to end at a leaf to count. At 7 we need 2 but have 7, so not valid. At 2 we need 2 and have 2, so it's valid. Then we add path into ans. More precisely, we add a copy of it. She writes "new list of path" (see Part B, Bug 2, for why).

Step 5: go left and right with a smaller target, and the same path

5 is not a leaf, so call the left child and then the right child. What do we send?

• Target: targetSum − root.val, since 5 is already part of every path below it (22 → 17).
• Path: the same path, which now holds [5]. The left child will add 4 to it, and later the right child will add 8.

Step 6: "Is it over?" Not yet: the dry run shows the missing line

The teacher asks if the code is complete, says not quite, and dry-runs to find out why. Follow the path list:

1. At 5 → path [5]. At 4 → [5, 4]. At 11 → [5, 4, 11]. At 7 → [5, 4, 11, 7].
2. 7 is a leaf, 2 ≠ 7, so nothing is saved. 7's children are None, so both calls return at once.
3. Now the call for 7 ends and we go back to 11, which next calls its right child 2.
4. Problem: path is still [5, 4, 11, 7]. Nobody removed the 7! When 2 is added, path becomes [5, 4, 11, 7, 2]. That isn't a real path, because 7 and 2 are siblings, not parent and child.

The fix: when a node's call is completely finished (after both children are done), remove that node from the path. In Python that's path.pop(), which removes the last item. (In Java she writes path.remove(path.size() - 1), which does the same thing.)

5Approach steps

1. Make the outer list ans = []. Call dfs(root, targetSum, []). Return ans.
2. In dfs: node is None → return.
3. Choose: append the node's value to path.
4. If it's a leaf and target == node.val → append a copy of path to ans.
5. Explore: dfs(left, target − val, path), then dfs(right, target − val, path).
6. Un-choose (backtrack): path.pop().

Choose → explore → un-choose is the general shape of backtracking. You'll see it again in subsets, permutations and many graph problems.

6Code (Python)

class Solution:
    def pathSum(self, root, targetSum):
        self.ans = []                         # outer list: every good path
        self.dfs(root, targetSum, [])         # path starts empty
        return self.ans

    def dfs(self, root, targetSum, path):
        if root is None:                      # nothing here, nothing to undo
            return
        path.append(root.val)                 # CHOOSE: step onto this node
        if root.left is None and root.right is None:      # leaf?
            if targetSum == root.val:                     # sum is exactly right
                self.ans.append(list(path))               # save a COPY
        self.dfs(root.left, targetSum - root.val, path)   # EXPLORE left
        self.dfs(root.right, targetSum - root.val, path)  # EXPLORE right
        path.pop()                            # UN-CHOOSE: step back off this node

The teacher also says you could carry a running sum instead (add each value, compare with targetSum at the leaf). Then you don't shrink the target. The backtracking part stays exactly the same:

class Solution:
    def pathSum(self, root, targetSum):
        self.ans = []
        self.dfs(root, 0, targetSum, [])
        return self.ans

    def dfs(self, root, s, targetSum, path):
        if root is None:
            return
        s += root.val                         # s is a number: no undo needed
        path.append(root.val)                 # path is shared: undo below
        if root.left is None and root.right is None and s == targetSum:
            self.ans.append(list(path))
        self.dfs(root.left, s, targetSum, path)
        self.dfs(root.right, s, targetSum, path)
        path.pop()

7Code line by line

8Dry run: follow the path list and the stack

Each call is (node, target it received). Watch the path column: it grows by one on the way down and shrinks by one on the way back up.

The stack is empty, path is back to [], and ans holds both good paths. Final answer: [[5, 4, 11, 2], [5, 8, 4, 5]] ✓

See the pattern: the stack height and the path length always move together. Every call on the stack has exactly one value in the path. That's the backtracking promise: each call cleans up its own footprint.

9Complexity & remember

• Time: the teacher says O(n), because each node is visited once and never again.
• Space: the stack (and the path) hold one node per level. Balanced → O(log n). Skewed → O(n), because then the number of levels is about n. In general O(h), not counting the answer list.

Part B · Backtracking up close: the two bugs to avoid

The two most common Path Sum II bugs come straight from the "one shared list" fact in Part 0. Seeing their actual output makes the fixes stick.

1Bug 1: forgetting path.pop()

class SolutionNoPop:
    def pathSum(self, root, targetSum):
        self.ans = []
        self.dfs(root, targetSum, [])
        return self.ans

    def dfs(self, root, targetSum, path):
        if root is None:
            return
        path.append(root.val)
        if root.left is None and root.right is None and targetSum == root.val:
            self.ans.append(list(path))
        self.dfs(root.left, targetSum - root.val, path)
        self.dfs(root.right, targetSum - root.val, path)
        # missing: path.pop()

The targets are still right (they're plain numbers), so it still finds the right leaves. But the saved lists are garbage, because nothing is ever rubbed out:

Output: [[5,4,11,7,2], [5,4,11,7,2,8,13,4,5]] ✗. This is exactly what the teacher spotted in her dry run.

2Bug 2: saving path itself instead of a copy

class SolutionNoCopy:
    def pathSum(self, root, targetSum):
        self.ans = []
        self.dfs(root, targetSum, [])
        return self.ans

    def dfs(self, root, targetSum, path):
        if root is None:
            return
        path.append(root.val)
        if root.left is None and root.right is None and targetSum == root.val:
            self.ans.append(path)          # BUG: same list, not a snapshot
        self.dfs(root.left, targetSum - root.val, path)
        self.dfs(root.right, targetSum - root.val, path)
        path.pop()

Here ans doesn't store two paths. It stores two names for the one shared list. The backtracking pops keep changing that list, and at the very end it's empty. So both entries show the empty list.

Output: [[], []] ✗. The teacher's "new list of path" is the fix: list(path) (or path[:], or path.copy()).

3The picture to keep in your head

                       path over time
  go down to 5     →  [5]
  go down to 4     →  [5, 4]
  go down to 11    →  [5, 4, 11]
  go down to 7     →  [5, 4, 11, 7]      leaf, wrong sum
  back up from 7   →  [5, 4, 11]         pop
  go down to 2     →  [5, 4, 11, 2]      leaf, right sum → photo (copy)
  back up from 2   →  [5, 4, 11]         pop
  back up from 11  →  [5, 4]             pop
  back up from 4   →  [5]                pop
  go down to 8     →  [5, 8]             ... and so on

The path list is used like a stack: push on the way down, pop on the way up. It always mirrors the call stack.

Part C · Revision page

root = TreeNode(5,
    TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2))),
    TreeNode(8, TreeNode(13), TreeNode(4, TreeNode(5), TreeNode(1))))

s = Solution()
print(s.pathSum(root, 22))     # [[5, 4, 11, 2], [5, 8, 4, 5]]
print(s.pathSum(root, 26))     # [[5, 8, 13]]
print(s.pathSum(root, 100))    # []
print(s.pathSum(None, 0))      # []

Based on this video: Path Sum II | DFS & Backtracking