Log inSign up
easyleetcodeNot Started

Path Sum

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 true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1 · Example 1: Valid Path Exists:

Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22 Tree: 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
Output: true
Explanation: Path 5 -> 4 -> 11 -> 2 sums to 5 + 4 + 11 + 2 = 22.

Example 2 · Example 2: No Valid Path:

Input: root = [1, 2, 3], targetSum = 5 Tree: 1 / \ 2 3
Output: false
Explanation: Paths are 1->2 (sum 3) and 1->3 (sum 4). Neither equals 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:

  • Verify leaf node condition (both left and right null).
  • Apply target subtraction pattern in tree recursion.
  • Leverage short-circuit OR (||) for early exit.

Pattern Recognition Trigger

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

Signals to Look For:

  • Root-to-leaf path sum equals target.
  • Decision problem returning boolean.
  • Leaf-terminated path verification.

Algorithmic Decision Tree:

  • If root == null -> return false.
  • If leaf (left == null && right == null) -> return targetSum == root.val.
  • return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val).

Connected Patterns:

Path Sum IIPath Sum IIIBinary Tree Maximum Path Sum

1. All Root-to-Leaf Path Accumulation

Intuition

Traverse tree collecting sum of every root-to-leaf path into a vector. Check if targetSum exists in vector.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: If root == null return false.
  2. Step 2: Collect all leaf sums using helper dfs(node, curSum, sums).
  3. Step 3: Check if targetSum is contained in sums list.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void getSums(TreeNode* node, int cur, vector<int>& sums) {
10 if (!node) return;
11 cur += node->val;
12 if (!node->left && !node->right) { sums.push_back(cur); return; }
13 getSums(node->left, cur, sums);
14 getSums(node->right, cur, sums);
15 }
16 bool hasPathSum(TreeNode* root, int targetSum) {
17 if (!root) return false;
18 vector<int> sums;
19 getSums(root, 0, sums);
20 for (int s : sums) if (s == targetSum) return true;
21 return false;
22 }
23};
24
25int main() {
26 // Sample driver execution
27 cout << "Execution completed successfully." << endl;
28 return 0;
29}
30

Time & Space Complexity

  • Time complexity: O(n) — Traverses all nodes and stores all leaf sums.
  • Space complexity: O(n) — List stores sums of all leaf nodes.

2. Iterative BFS with Queue of (Node, RemainingSum)

Intuition

Push (root, targetSum - root.val) into queue. While not empty: pop (node, rem). If node is leaf and rem == 0, return true. Otherwise push children with rem - child.val.

When to apply: Iterative queue-based solution.

Algorithm

  1. Step 1: If root == null return false.
  2. Step 2: Queue stores (node, remSum). Push (root, targetSum - root.val).
  3. Step 3: Pop (node, rem). If leaf and rem == 0, return true.
  4. Step 4: Push children with updated rem. Return false if queue empties.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 bool hasPathSum(TreeNode* root, int targetSum) {
10 if (!root) return false;
11 queue<pair<TreeNode*, int>> q;
12 q.push({root, targetSum - root->val});
13 while (!q.empty()) {
14 auto [node, rem] = q.front(); q.pop();
15 if (!node->left && !node->right && rem == 0) return true;
16 if (node->left) q.push({node->left, rem - node->left->val});
17 if (node->right) q.push({node->right, rem - node->right->val});
18 }
19 return false;
20 }
21};
22
23int main() {
24 // Sample driver execution
25 cout << "Execution completed successfully." << endl;
26 return 0;
27}
28

Time & Space Complexity

  • Time complexity: O(n) — Stops as soon as path is found.
  • Space complexity: O(w) — Queue holds level width w.

3. Clean Recursive DFS with Target Subtraction

Intuition

If root is null return false. If leaf (both left and right null), return targetSum == root.val. Otherwise return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val).

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: If root == null return false.
  2. Step 2: If root.left == null && root.right == null: return targetSum == root.val.
  3. Step 3: Return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val).

Path Sum 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: Inspect root 5
Visual state
Values and pointers at this exact step
tree
Root
5
L
4 (rem: 4)
R
8

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

rem: 4: 4
Check / comparison
Remaining target: 4
Decision / next transition
Recurse on left child 4.
Why this step matters

Step 1: Inspect root 5. targetSum = 9. Subtraction: remaining = 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 {
8public:
9 bool hasPathSum(TreeNode* root, int targetSum) {
10 if (!root) return false;
11 if (!root->left && !root->right) return targetSum == root->val;
12 return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
13 }
14};
15
16int main() {
17 // Sample driver execution
18 cout << "Execution completed successfully." << endl;
19 return 0;
20}
21

Time & Space Complexity

  • Time complexity: O(n) — Visits at most n nodes with early exit.
  • Space complexity: O(h) — Call stack bounded by tree height h.

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.All Path Sums CollectionO(n)O(n)Collect all leaf path sums into list and search.No early termination.
2.Iterative BFS QueueO(n)O(w)Queue holds pairs of node and remaining sum.Queue memory.
3.Clean Recursive DFS with Target SubtractionOptimalO(n)O(h)Subtract node.val recursively; leaf returns target == val; short-circuit OR.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Empty tree: root = [], targetSum = 0 -> returns false (no path exists).
  • Single node matching target: root = [1], targetSum = 1 -> returns true.
  • Single node not matching: root = [1], targetSum = 2 -> returns false.
  • Negative node values and negative targets: handled naturally by subtraction.

Interview Tips & Best Practices

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

  1. Clarify that an empty tree returns false even if targetSum is 0 (an empty tree has no root-to-leaf paths).
  2. Emphasize that a node with only one child is NOT a leaf; path cannot terminate there.

Quick Comprehension Check

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

1.Why does the base case if (root == null) return false return false even when targetSum == 0?

Back to DSA Sheet