← Back to DSA Animator
Path Sum II LC #113 Medium DFS Backtracking · All Paths
Problem

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of node values equals targetSum.

Example 1
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Example 2
Input: root = [1,2,3], targetSum = 5
Output: []
Constraints: 0 ≤ nodes ≤ 5000  |  −1000 ≤ targetSum ≤ 1000
Try Examples
Custom:
Approach
DFS Backtracking — Find ALL Root-to-Leaf Paths
Add node to path on entry, subtract from remainder. At leaf if rem==0, record path copy. Then recurse left and right. Backtrack: remove last node on return.
Binary Tree
Current Path
Path starts at root…
sum:0 remaining:— target:—
Found Paths (0)
No paths found yet…
Recursion Stack
Variables
Current Node
—
rem
—
path.size
0
paths found
0
Step Logic
Press ▶ Play or Next Step to begin.
🎉
Ready
0 / 0
Select an example and press Play.
Algorithm
1
path.add(node.val); rem -= node.val
2
Leaf AND rem == 0 → add copy of path to result
3
Recurse left, then recurse right
4
Backtrack: path.remove(last) — restore state
Time
O(n²)
Space
O(h)
Why Backtracking?

Unlike Path Sum I (stop at first match), we must find all paths. Backtracking lets us reuse a single path list: add a node on entry, explore both subtrees, then remove on exit. This gives O(h) space for the path instead of O(n) per path.