Path Sum II

Path Sum II

What is this problem about?

The Path Sum II problem asks you to find all root-to-leaf paths in a binary tree where the sum of node values equals a target. Return all such paths. This coding problem uses DFS with backtracking to collect all valid paths. The DFS, backtracking, binary tree, and tree interview pattern is the core.

Why is this asked in interviews?

Microsoft, Meta, Amazon, TikTok, Google, Bloomberg, and DoorDash ask this because it extends Path Sum I from a boolean check to collecting all valid paths. It tests backtracking on trees — maintaining a current path, adding to results at valid leaves, and restoring state on backtrack.

Algorithmic pattern used

DFS backtracking. Maintain current_path list. At each node: append node.val to current_path, subtract from remaining. If at a leaf and remaining=0: add a copy of current_path to results. Recurse on left and right children. Backtrack: remove node.val from current_path.

Example explanation

Tree: 5→(4→(11→(7,2)),8→(13,4→(5,1))). target=22. Valid paths: 5→4→11→2 (sum=22), 5→8→4→5? (=22). Result: [[5,4,11,2],[5,8,4,5]].

Common mistakes candidates make

• Not making a copy when adding to results (list is shared and gets modified).
• Not backtracking (not removing the last element after returning from recursion).
• Checking sum at non-leaf nodes (must only check at leaves).
• Off-by-one in path construction.

Interview preparation tip

Tree backtracking is a critical skill. The pattern: push, recurse, pop (backtrack). Always add a copy of the current path to results — not the path itself. Practice this pattern on all "find all paths" tree problems. The key insight: backtracking on trees is implicit in recursion — the call stack maintains the path, and explicit pop/append manages the shared data structure.