Path Sum II

74.1k
0

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths whose node values add up exactly to targetSum.

Each returned path should contain the node values in order from the root to the corresponding leaf.

If no root-to-leaf path has the required sum, return an empty list.

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]]

Explanation:
The root-to-leaf paths 5 -> 4 -> 11 -> 2 and 5 -> 8 -> 4 -> 5 both have a sum of 22.

Example 2

Input:
root = [1, 2, 3], targetSum = 5

Output:
[]

Explanation:
The root-to-leaf path sums are 1 + 2 = 3 and 1 + 3 = 4. Neither equals 5, so no valid path exists.

Brute Force Approach

A direct way to solve the problem is to first generate every root-to-leaf path without considering targetSum.

A list named currentPath is maintained because it represents the sequence of values on the currently active root-to-node path. Another collection named allPaths is used because it stores every complete root-to-leaf path discovered during DFS.

Whenever a leaf is reached, a copy of currentPath is stored in allPaths. A copy is required because currentPath continues to change during backtracking, and storing the same reference would cause previously recorded paths to be modified.

After all root-to-leaf paths have been generated, the sum of every path is calculated and only those whose sum equals targetSum are added to the final result.

This approach is easy to understand, but it stores and checks many paths that may never become part of the answer.

Algorithm

  • If the tree is empty, an empty result is returned because no root-to-leaf path exists.

  • A list named currentPath is maintained to represent the currently active root-to-node route, while allPaths is maintained to store every completed root-to-leaf path.

  • During DFS, the current node's value is appended to currentPath so that the active path remains updated.

  • If the current node is a leaf, a copy of currentPath is inserted into allPaths because the complete root-to-leaf path must be preserved even after currentPath changes during backtracking.

  • After the node's subtree has been processed, the current node is removed from currentPath so that the parent's path state is restored.

  • Once DFS is completed, the sum of every path stored in allPaths is calculated.

Dry Run

Path Sum II Brute Force Appraoch Dry Run.png

Path Sum II Brute Force Appraoch Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
private:
// Generates every complete root-to-leaf path.
void collectPaths(
TreeNode* node,
vector<int>& currentPath,
vector<vector<int>>& allPaths
) {
if (node == nullptr) {
return;
}
currentPath.push_back(node->val);
if (
node->left == nullptr &&
node->right == nullptr
) {
// A copy is stored because currentPath
// changes later during backtracking.
allPaths.push_back(currentPath);
} else {
collectPaths(
node->left,
currentPath,
allPaths
);
collectPaths(
node->right,
currentPath,
allPaths
);
}
// The current node is removed so the
// parent's path is restored for another branch.
currentPath.pop_back();
}
public:
// Generates all paths first and then
// keeps only those matching targetSum.
vector<vector<int>> pathSum(
TreeNode* root,
int targetSum
) {
vector<vector<int>> paths;
if (root == nullptr) {
return paths;
}
vector<vector<int>> allPaths;
vector<int> currentPath;
collectPaths(
root,
currentPath,
allPaths
);
// Every generated path is checked
// separately against the required sum.
for (const auto& path : allPaths) {
long long pathSumValue = 0;
for (int value : path) {
pathSumValue += value;
}
if (pathSumValue == targetSum) {
paths.push_back(path);
}
}
return paths;
}
};
int main() {
TreeNode* root = new TreeNode(5);
root->left = new TreeNode(4);
root->right = new TreeNode(8);
root->left->left = new TreeNode(11);
root->left->left->left = new TreeNode(7);
root->left->left->right = new TreeNode(2);
root->right->left = new TreeNode(13);
root->right->right = new TreeNode(4);
root->right->right->left = new TreeNode(5);
root->right->right->right = new TreeNode(1);
int targetSum = 22;
Solution solution;
vector<vector<int>> paths =
solution.pathSum(root, targetSum);
for (const auto& path : paths) {
for (int value : path) {
cout << value << " ";
}
cout << endl;

Complexity Analysis

Let N be the number of nodes in the binary tree, H be the height of the tree, and P be the total number of node values contained across all root-to-leaf paths generated.

Time Complexity: O(N + P). Every node is visited during DFS, while copying and later checking all generated root-to-leaf paths requires a total of O(P) work. In the worst case, P can grow to O(N × H).

Space Complexity: O(H + P), excluding the final returned answer. The recursion stack and currentPath require at most O(H) space, while storing every generated root-to-leaf path in allPaths requires O(P) space.

Optimal Approach

Generating and storing every root-to-leaf path is unnecessary because only paths whose sum equals targetSum need to be returned.

A list named currentPath is maintained because it represents the active path from the root to the current node.

A variable named remainingSum is also maintained because it represents how much of targetSum still needs to be contributed by the current node and the nodes below it.

Initially:

remainingSum = targetSum

Whenever a node is visited, its value is subtracted from remainingSum.

If a leaf is reached and the updated remainingSum becomes 0, the current path is valid. A copy of currentPath is stored because the original list will continue changing during backtracking.

The sum condition is checked only at a leaf because the problem requires a complete root-to-leaf path. Reaching the required sum at an internal node is not sufficient.

After the children of a node have been processed, its value is removed from currentPath so that the path state is restored for the next branch.

Algorithm

  • A list named currentPath is maintained to represent the active root-to-node route, while paths is maintained to store only the valid root-to-leaf paths.

  • If the current node is null, the recursive call is terminated because no path can be extended through an empty subtree.

  • When a node is visited, its value is appended to currentPath, and its value is subtracted from remainingSum, where remainingSum represents the amount still required to reach targetSum.

  • If the current node is a leaf, the path is considered valid only when remainingSum becomes 0. In that case, a copy of currentPath is inserted into paths so later backtracking does not modify the stored result.

  • If the node is not a leaf, the left and right subtrees are explored recursively using the updated remainingSum.

  • After the current node and its descendants have been processed, the current node is removed from currentPath so that the parent's path state is restored.

  • DFS is started from the root with targetSum as the initial remainingSum, and all valid paths stored in paths are returned.

Dry Run

Path Sum II Optimal Appraoch Dry Run.png

Path Sum II Optimal Appraoch Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
private:
// Tracks the active path and the sum
// still required to reach targetSum.
void dfs(
TreeNode* node,
long long remainingSum,
vector<int>& currentPath,
vector<vector<int>>& paths
) {
if (node == nullptr) {
return;
}
currentPath.push_back(node->val);
remainingSum -= node->val;
// The sum is checked only at a leaf
// because the path must end at a leaf.
if (
node->left == nullptr &&
node->right == nullptr
) {
if (remainingSum == 0) {
// A copy is stored because currentPath
// changes later during backtracking.
paths.push_back(currentPath);
}
} else {
dfs(
node->left,
remainingSum,
currentPath,
paths
);
dfs(
node->right,
remainingSum,
currentPath,
paths
);
}
// The current node is removed to restore
// the path before another branch is explored.
currentPath.pop_back();
}
public:
// Returns every root-to-leaf path
// whose values sum to targetSum.
vector<vector<int>> pathSum(
TreeNode* root,
int targetSum
) {
vector<vector<int>> paths;
vector<int> currentPath;
dfs(
root,
targetSum,
currentPath,
paths
);
return paths;
}
};
int main() {
TreeNode* root = new TreeNode(5);
root->left = new TreeNode(4);
root->right = new TreeNode(8);
root->left->left = new TreeNode(11);
root->left->left->left = new TreeNode(7);
root->left->left->right = new TreeNode(2);
root->right->left = new TreeNode(13);
root->right->right = new TreeNode(4);
root->right->right->left = new TreeNode(5);
root->right->right->right = new TreeNode(1);
int targetSum = 22;
Solution solution;
vector<vector<int>> paths =
solution.pathSum(root, targetSum);
for (const auto& path : paths) {
for (int value : path) {
cout << value << " ";
}
cout << endl;
}
return 0;
}

Complexity Analysis

Let N be the number of nodes in the binary tree, H be the height of the tree, and K be the total number of node values contained across all valid paths returned in the answer.

Time Complexity: O(N + K). Every node is visited once, while copying valid paths into the result requires a total of O(K) additional work.

Space Complexity: O(H), excluding the returned paths. The recursion stack and currentPath contain at most one root-to-leaf route at a time. This becomes O(N) for a skewed tree and O(log N) for a balanced tree.

Interview follow-up Questions

Path Sum only asks whether at least one valid root-to-leaf path exists. Path Sum II requires returning every path whose sum equals targetSum.

Binary Tree

Read Similar Blogs

Binary Tree

Parent and Distance - Introduction

Parent and Distance in a Binary Tree A binary tree normally stores connections from a node to its children: Left child Right child These connections make downward traversal straightforward. However...

117.9k
Binary Tree

Check If a Binary Tree Is a Subtree of Another Tree

Given the roots of two binary trees, root and subRoot , determine whether subRoot appears as a subtree of root . A subtree must match an entire tree section starting from some node in root , includ...

67.9k
Binary Tree

Count Nodes in a Complete Binary Tree

Given the root of a complete binary tree , determine the total number of nodes present in the tree. In a complete binary tree: Every level except possibly the last is completely filled. Nodes in th...

54.2k
Comments0