Path Sum

118.8k
0

Given the root of a binary tree and an integer targetSum, determine whether there exists at least one path that:

  • starts from the root,

  • ends at a leaf node, and

  • has a sum of node values equal to targetSum.

Return true if such a path exists. Otherwise, return false.

A leaf is a node that has neither a left child nor a right child.

Example 1

Input:
root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22

Output:
true

Explanation:
The root-to-leaf path 5 -> 4 -> 11 -> 2 has a sum of 22, so a valid path exists.

Example 2

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

Output:
false

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

Example 3

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

Output:
false

Explanation:
Although the root itself has value 1, it is not a leaf because it has a child. Therefore, no valid root-to-leaf path has sum 1.

Brute Force Approach

A direct way to solve the problem is to explicitly examine every root-to-leaf path.

A list currentPath is maintained to represent the sequence of node values from the root to the currently visited node. Whenever a leaf is reached, all values stored in currentPath are added and compared with targetSum.

If any leaf produces the required sum, true is returned.

This follows the problem definition closely, but repeatedly calculating the sum of complete paths creates unnecessary work because values near the root may be added again for several different leaf paths.

Algorithm

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

  • A list named currentPath is maintained because it represents the sequence of node values on the currently active root-to-node path.

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

  • If the current node is a leaf, the values stored in currentPath are summed and the result is compared with targetSum.

  • If the calculated sum matches targetSum, true is returned; otherwise, the remaining root-to-leaf paths are explored.

  • Before a recursive call returns to its parent, the current node is removed from currentPath so that the path state is restored for the next branch.

  • If every root-to-leaf path has been examined without finding the required sum, false is returned.

Dry Run

Path Sum Brute Force Dry Run .png

Path Sum Brute Force 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:
// Checks every root-to-leaf path
// by explicitly calculating its sum.
bool dfs(
TreeNode* node,
int targetSum,
vector<int>& currentPath
) {
// An empty subtree cannot
// form a valid path.
if (node == nullptr) {
return false;
}
currentPath.push_back(node->val);
// The sum is checked only at a leaf
// because the path must end there.
if (
node->left == nullptr &&
node->right == nullptr
) {
int pathSum = 0;
for (int value : currentPath) {
pathSum += value;
}
if (pathSum == targetSum) {
currentPath.pop_back();
return true;
}
}
// Both branches are explored until
// a valid root-to-leaf path is found.
if (
dfs(node->left, targetSum, currentPath) ||
dfs(node->right, targetSum, currentPath)
) {
currentPath.pop_back();
return true;
}
// The current node is removed so
// the parent's path is restored.
currentPath.pop_back();
return false;
}
public:
// Determines whether any root-to-leaf
// path has the required sum.
bool hasPathSum(
TreeNode* root,
int targetSum
) {
if (root == nullptr) {
return false;
}
vector<int> currentPath;
return dfs(
root,
targetSum,
currentPath
);
}
};
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->right = new TreeNode(1);
int targetSum = 22;
Solution solution;
cout << boolalpha
<< solution.hasPathSum(root, targetSum)
<< endl;
return 0;
}

Complexity Analysis

Let N be the number of nodes in the binary tree and H be the height of the tree.

Time Complexity: O(N × H) in the worst case. Every node may be visited during DFS, and whenever a leaf is reached, summing currentPath may require processing up to H values.

Space Complexity: O(H), where H is the height of the binary tree. The recursion stack and currentPath can each contain at most one root-to-leaf path at a time.

Optimal Approach 1

Storing the complete path is unnecessary because the problem only asks whether its sum equals targetSum.

Instead, a variable remainingSum is maintained. The name represents the amount that still needs to be contributed by the current node and the nodes below it for the original targetSum to be reached.

Initially:

remainingSum = targetSum

Whenever a node is visited, its value is subtracted from remainingSum. The updated value therefore represents the sum still required from the remaining part of the path.

When a leaf is reached, the path is valid only if the updated remainingSum becomes exactly 0.

The leaf condition is essential because reaching the required sum at an internal node does not form a valid root-to-leaf path.

Algorithm

  • If the current node is null, false is returned because no valid path can continue through an empty subtree.

  • A variable remainingSum is maintained because it represents the portion of targetSum that still needs to be contributed by the current node and its descendants.

  • The current node's value is subtracted from remainingSum so that only the amount required from nodes below the current position remains.

  • If the current node is a leaf, whether remainingSum equals 0 is returned because the complete root-to-leaf path has now been formed.

  • If the node is not a leaf, the left subtree is searched recursively using the updated remainingSum.

  • The right subtree is also searched using the same updated value if a valid path has not already been found.

  • true is returned if either subtree contains a root-to-leaf path that completes the required sum; otherwise, false is returned.

Dry Run

Path Sum Optimal Appraoch 1 Dry Run .png

Path Sum Optimal Appraoch 1 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 how much of the target sum
// is still required along the path.
bool dfs(
TreeNode* node,
int remainingSum
) {
// An empty subtree cannot
// complete a valid path.
if (node == nullptr) {
return false;
}
remainingSum -= node->val;
// The remaining sum must become zero
// only when a leaf is reached.
if (
node->left == nullptr &&
node->right == nullptr
) {
return remainingSum == 0;
}
// Either subtree may complete
// the required root-to-leaf sum.
return dfs(
node->left,
remainingSum
) || dfs(
node->right,
remainingSum
);
}
public:
// Determines whether any root-to-leaf
// path has the required sum.
bool hasPathSum(
TreeNode* root,
int targetSum
) {
return dfs(
root,
targetSum
);
}
};
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->right = new TreeNode(1);
int targetSum = 22;
Solution solution;
cout << boolalpha
<< solution.hasPathSum(root, targetSum)
<< endl;
return 0;
}

Complexity Analysis

Let N be the number of nodes in the binary tree and H be the height of the tree.

Time Complexity: O(N), where N is the number of nodes in the binary tree. Each node is visited at most once, although traversal may terminate earlier when a valid path is found.

Space Complexity: O(H), where H is the height of the binary tree, due to the recursive call stack. This becomes O(N) for a skewed tree and O(log N) for a balanced tree.

Optimal Approach 2

The same running-sum idea can also be implemented without recursion.

A stack named nodesStack is used because it stores the nodes that still need to be processed during iterative DFS. Instead of storing only the node, each stack entry contains:

(node, currentPathSum)

Here, currentPathSum represents the sum of all node values from the root to that particular node.

Whenever a leaf is removed from nodesStack, its accumulated path sum can be compared directly with targetSum.

Each child receives its parent's accumulated sum plus its own value, allowing the required path information to be preserved without storing the complete sequence of nodes.

Algorithm

  • If root is null, false is returned because an empty tree contains no root-to-leaf path.

  • A stack named nodesStack is initialized because it stores nodes that are waiting to be processed along with their accumulated root-to-node sums.

  • The pair (root, root.value) is inserted into nodesStack, where the second value represents the initial root-to-node sum.

  • While nodesStack is not empty, one (node, currentPathSum) entry is removed for processing.

  • If the removed node is a leaf and currentPathSum equals targetSum, true is returned because a valid root-to-leaf path has been found.

  • For every existing child, a new sum is formed as currentPathSum + child.value, and the child is inserted into nodesStack with this updated root-to-child sum.

  • If nodesStack becomes empty without finding a valid leaf, false is returned.

Dry Run

Path Sum Optimal Appraoch 2 Dry Run .png

Path Sum Optimal Appraoch 2 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 {
public:
// Uses iterative DFS while storing
// each node with its root-to-node sum.
bool hasPathSum(
TreeNode* root,
int targetSum
) {
if (root == nullptr) {
return false;
}
// nodesStack stores pending nodes
// together with their path sums.
stack<pair<TreeNode*, long long>> nodesStack;
nodesStack.push({
root,
root->val
});
// Every stack entry contains the
// accumulated sum up to that node.
while (!nodesStack.empty()) {
auto [node, currentPathSum] =
nodesStack.top();
nodesStack.pop();
// The target is checked only at leaves
// because the path must end at a leaf.
if (
node->left == nullptr &&
node->right == nullptr &&
currentPathSum == targetSum
) {
return true;
}
// Each child receives its parent's sum
// plus its own value.
if (node->right != nullptr) {
nodesStack.push({
node->right,
currentPathSum + node->right->val
});
}
if (node->left != nullptr) {
nodesStack.push({
node->left,
currentPathSum + node->left->val
});
}
}
return false;
}
};
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->right = new TreeNode(1);
int targetSum = 22;
Solution solution;
cout << boolalpha
<< solution.hasPathSum(root, targetSum)
<< endl;
return 0;
}

Complexity Analysis

Let N be the number of nodes in the binary tree and H be the height of the tree.

Time Complexity: O(N), where N is the number of nodes in the binary tree. Every node is pushed onto and removed from nodesStack at most once.

Space Complexity: O(H), where H is the height of the binary tree, for the pending nodes stored during depth-first traversal. In the worst case of a skewed tree, this bound can become O(N).

FAQs

Q1. Why must the path end at a leaf node?

The problem specifically requires a root-to-leaf path. Therefore, obtaining targetSum at an internal node is not sufficient if that node still has a child.

Q2. Why is the current node's value subtracted from remainingSum?

After the current node has been included in the path, only the remaining amount needs to be contributed by the nodes below it. This allows the required sum to be tracked without storing the complete path.

Q3. Can the tree contain negative node values?

Yes. These DFS approaches work correctly with negative values because they do not assume that the running or remaining sum changes in only one direction.

Q4. Can traversal stop as soon as one valid path is found?

Yes. Only the existence of such a path is required, so the remaining tree does not need to be processed once a valid root-to-leaf path has been found.

Q5. How is this different from printing all root-to-leaf paths?

Printing paths requires storing the actual sequence of nodes. Path Sum only requires determining whether a required total exists, so maintaining a running or remaining sum is sufficient.

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

118.4k
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...

68.4k
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...

57.1k
Comments0