Log inSign up
mediumleetcodeNot Started

Path Sum II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A leaf is a node with no children.

Example 1 · Example 1: Multiple Valid Paths:

Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1], targetSum = 22 Tree: 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1
Output: [[5, 4, 11, 2], [5, 8, 4, 5]]
Explanation: Two paths sum to 22: 5+4+11+2=22 and 5+8+4+5=22.

Example 2 · Example 2: No Matching Paths:

Input: root = [1, 2, 3], targetSum = 5 Tree: 1 / \ 2 3
Output: []
Explanation: Paths 1->2 (sum 3) and 1->3 (sum 4) do not equal 5.

Constraints:

  • The number of nodes in the tree is in the range [0, 5000].
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master mutable array backtracking on trees.
  • Prevent memory blowup by sharing a single path buffer.
  • Handle negative values and multiple matching branches.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find all root-to-leaf paths whose sum equals target.
  • List of path lists output format.
  • Backtracking state accumulation.

Algorithmic Decision Tree:

  • currentPath.push(node.val).
  • If leaf and val == target -> result.push([...currentPath]).
  • dfs(left, target - val); dfs(right, target - val).
  • currentPath.pop().

Connected Patterns:

Path SumPath Sum IIIBinary Tree Paths

1. Pass Path by Value Recursion

Intuition

Pass path vector by value to children. When reaching a matching leaf, add path to result list.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: If root == null return.
  2. Step 2: Append root.val to path copy.
  3. Step 3: If leaf and targetSum == root.val, append path to res.
  4. Step 4: Recurse left and right passing path copy.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void dfs(TreeNode* node, int sum, vector<int> path, vector<vector<int>>& res) {
10 if (!node) return;
11 path.push_back(node->val);
12 if (!node->left && !node->right && node->val == sum) {
13 res.push_back(path);
14 return;
15 }
16 dfs(node->left, sum - node->val, path, res);
17 dfs(node->right, sum - node->val, path, res);
18 }
19 vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
20 vector<vector<int>> res;
21 dfs(root, targetSum, {}, res);
22 return res;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n * h) — Copying path arrays of size up to h at each node.
  • Space complexity: O(n * h) — Stack frames hold full copies of paths.

2. BFS with Queue Storing (Node, Path, RemSum)

Intuition

Store tuples of (node, pathList, remSum) in queue. When popping matching leaf, append pathList to result.

When to apply: Iterative alternative avoiding recursion stack limits.

Algorithm

  1. Step 1: If root == null return [].
  2. Step 2: Queue stores tuples (node, path, rem).
  3. Step 3: Pop item. If matching leaf, add path to res.
  4. Step 4: Push children with updated path and rem.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
10 if (!root) return {};
11 vector<vector<int>> res;
12 queue<tuple<TreeNode*, vector<int>, int>> q;
13 q.push({root, {root->val}, targetSum - root->val});
14 while (!q.empty()) {
15 auto [node, path, rem] = q.front(); q.pop();
16 if (!node->left && !node->right && rem == 0) {
17 res.push_back(path);
18 }
19 if (node->left) {
20 vector<int> lp = path; lp.push_back(node->left->val);
21 q.push({node->left, lp, rem - node->left->val});
22 }
23 if (node->right) {
24 vector<int> rp = path; rp.push_back(node->right->val);
25 q.push({node->right, rp, rem - node->right->val});
26 }
27 }
28 return res;
29 }
30};
31
32int main() {
33 // Sample driver execution
34 cout << "Execution completed successfully." << endl;
35 return 0;
36}
37

Time & Space Complexity

  • Time complexity: O(n * h) — Path duplication per queue entry.
  • Space complexity: O(n * h) — Queue holds paths for up to w nodes.

3. Backtracking DFS with Shared Path Vector

Intuition

Maintain a single mutable path array across the entire traversal. Push node.val on descending; if leaf and matches, push copy of path to answer. Recurse left and right. Pop node.val on backtracking.

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: Maintain shared vector curPath.
  2. Step 2: curPath.push_back(node.val).
  3. Step 3: If leaf and node.val == rem: res.push_back(curPath).
  4. Step 4: Recurse left and right with rem - node.val.
  5. Step 5: curPath.pop_back().

Backtracking DFS Trace for root = [5, 4, 8], targetSum = 9

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: At root 5
Visual state
Values and pointers at this exact step
tree
Root
5
L
4
R
8

Node order shown; add connections to display explicit tree edges.

path: 4
Check / comparison
path: [5], remaining: 4
Decision / next transition
Explore left branch 4.
Why this step matters

Step 1: At root 5. path = [5]. Remaining target = 9 - 5 = 4. Recurse to left child 4.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 vector<vector<int>> res;
9 vector<int> path;
10 void dfs(TreeNode* node, int rem) {
11 if (!node) return;
12 path.push_back(node->val);
13 if (!node->left && !node->right && node->val == rem) {
14 res.push_back(path);
15 } else {
16 dfs(node->left, rem - node->val);
17 dfs(node->right, rem - node->val);
18 }
19 path.pop_back();
20 }
21public:
22 vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
23 dfs(root, targetSum);
24 return res;
25 }
26};
27
28int main() {
29 // Sample driver execution
30 cout << "Execution completed successfully." << endl;
31 return 0;
32}
33

Time & Space Complexity

  • Time complexity: O(n) — Every node visited once; path copied only on valid leaf matches.
  • Space complexity: O(h) — Shared path array and recursion stack both take O(h) space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Pass Path by ValueO(n * h)O(n * h)Copy path array at each recursive invocation.Array copying.
2.BFS Queue PathsO(n * h)O(n * h)Queue holds paths for all frontier nodes.Queue allocations.
3.Backtracking with Shared VectorOptimalO(n)O(h)Single shared mutable path buffer with push/pop.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Empty tree: returns [].
  • Single node matching target: returns [[node.val]].
  • Negative targets and values: handled naturally by subtraction.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain why pushing and popping in a single vector is O(h) space compared to passing vector by value which is O(n * h).
  2. Remember that copying currentPath into result takes O(h) per valid path.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is a single shared mutable array with push and pop (backtracking) more memory efficient than passing arrays by value?

Back to DSA Sheet