Path Sum II

Find all root-to-leaf paths where each path's sum equals the targetSum.

10 min read

Solve on LeetCode

Examples

Input:root = [5,4,8,11,null,13,4,7,2,5,1], targetSum = 22

Output:[[5,4,11,2],[5,8,4,5]]

Explain:

Two paths sum to 22.

Problem Understanding

Unlike Path Sum I, we need to return all distinct paths that satisfy the condition, not just a boolean.

Since we need to store the actual path (list of nodes), we'll need to maintain a current_path list as we traverse. When we hit a valid leaf, we add a copy of current_path to our global result.

Algorithm Strategy (Backtracking)

We use DFS with Backtracking.

State: Maintain current_path list and remaining_sum.
Action: On visiting node, add node.val to current_path.
Check: If leaf & node.val == remaining_sum, save a copy of the path.
Recurse: Call left and right children.
Backtrack: Crucially, pop the last element (node.val) from current_path before returning to parent. This cleans up the state for other branches.

Interactive Visualization

Step 1 / 1

Empty Heap

Initializing...

Custom Input

Observe the 'Backtrack' step where the node is removed from the current path.

Previous Problem

Count Good Nodes in Binary Tree

Next Problem

Binary Tree Right Side View

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.