Path Sum II

Master this topic with zero to advance depth.

Path Sum II

All root-to-leaf paths summing to target.

Medium

Approach 1

Level I: DFS with List Copying

Intuition

To find all root-to-leaf paths that sum to a target, we can use Depth First Search (DFS). In this basic version, each time we recurse, we create a new copy of the current path. This is simpler to implement but less space-efficient than backtracking.

Thought Process

At each node, subtract node.val from the remaining target.
If it's a leaf node and remainingTarget == 0, add the current path to the result list.
Recurse to left and right children with a fresh copy of the current path.

⏱ O(N^2) (In the worst case of a skewed tree, we copy the path at each node)💾 O(N^2) (Storing many path lists)

Detailed Dry Run

Tree	Target	Path	Remaining	Action
5	22	[5]	17	Recurse
4	17	[5, 4]	13	Recurse
11	13	[5, 4, 11]	2	Recurse (to 2)
2	2	[5, 4, 11, 2]	0	SUCCESS!

java

import java.util.*;

public class Main {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, targetSum, new ArrayList<>(), res);
        return res;
    }
    private void dfs(TreeNode node, int sum, List<Integer> path, List<List<Integer>> res) {
        if (node == null) return;
        List<Integer> currentPath = new ArrayList<>(path);
        currentPath.add(node.val);
        if (node.left == null && node.right == null && sum == node.val) {
            res.add(currentPath);
            return;
        }
        dfs(node.left, sum - node.val, currentPath, res);
        dfs(node.right, sum - node.val, currentPath, res);
    }
}

Approach 2

Level II: Iterative BFS (Queue with State)

Intuition

We can use a Queue of Triplets (node, currentPath, currentSum) to simulate BFS. For each node, we push its children along with the updated path and sum. This avoids recursion entirely while still exploring the tree level by level.

Thought Process

Store state as [node, path_list, rem_sum].
When reaching a leaf, if rem_sum == node.val, save path.
Push children with path + [node.val] and rem_sum - node.val.

⏱ O(N^2)💾 O(N^2)

Detailed Dry Run

Queue: [(5, [], 22)]. Pop 5, Push (4, [5], 17) and (8, [5], 17). Pop 4, Push (11, [5, 4], 13)...

java

public class Main {
    class State { TreeNode node; List<Integer> path; int sum; State(TreeNode n, List<Integer> p, int s) {node=n; path=p; sum=s;} }
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<State> q = new LinkedList<>();
        q.add(new State(root, new ArrayList<>(), targetSum));
        while (!q.isEmpty()) {
            State s = q.poll();
            List<Integer> newPath = new ArrayList<>(s.path);
            newPath.add(s.node.val);
            if (s.node.left == null && s.node.right == null && s.sum == s.node.val) {
                res.add(newPath);
            }
            if (s.node.left != null) q.add(new State(s.node.left, newPath, s.sum - s.node.val));
            if (s.node.right != null) q.add(new State(s.node.right, newPath, s.sum - s.node.val));
        }
        return res;
    }
}

Approach 3

Level III: Optimal (Backtracking)

Intuition

Thought Process

Instead of copying the array at every step, we use a single global list and perform backtracking. We add the current node to the list, recurse, and then remove the current node (the last element) before returning from the function call.

Patterns

DFS + Backtracking: Keep state clean for previous caller by undoing changes.

Complexity

Time: $O(N)$ (Every node visited once)
Space: $O(H)$ (For the recursive stack and the single path list)

⏱ O(N)💾 O(H)

Detailed Dry Run

Action	Path	Sum (Remaining)
Visit 5	[5]	17
Visit 4	[5, 4]	13
Visit 11	[5, 4, 11]	2
Pop 11	[5, 4]	13

java

public class Main {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(root, targetSum, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(TreeNode node, int sum, List<Integer> path, List<List<Integer>> res) {
        if (node == null) return;
        path.add(node.val);
        if (node.left == null && node.right == null && sum == node.val) {
            res.add(new ArrayList<>(path));
        } else {
            backtrack(node.left, sum - node.val, path, res);
            backtrack(node.right, sum - node.val, path, res);
        }
        path.remove(path.size() - 1);
    }
}

⚠️ Common Pitfalls & Tips

You still need to copy the list when adding it to the result (res.add(new ArrayList<>(path))), otherwise all paths in the result will end up empty at the end of the process!

← Previous QuestionBinary Tree Zigzag Level Order Traversal

Next Question →Kth Smallest Element in a BST

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.