DSA AnimatorDSA animations
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.

How to solve Path Sum II

LeetCode 113 · Medium · Tree · Pattern: DFS Backtracking

Why the obvious approach is slow

Copying the whole path at every node wastes memory and time. We can keep one shared path and undo each step on the way back.

The key idea

Keep a path list and a remaining target. When you enter a node, add it to the path and subtract its value. At a leaf with remaining 0, save a copy of the path. When you leave a node, remove it from the path, which is the backtracking step.

Remember

Add on the way down, remove on the way back up. Only copy the path when you actually save it.

Run the animation above on your own input, or watch the 1:51 video explanation of Path Sum II with a dry run and Java code.

More Tree problems