Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Path Sum III

Try it yourself
MediumProblemExternal link

Description

Given the root of a binary tree and an integer targetSum, return how many paths in the tree have values that add up to targetSum.

A path doesn't have to start at the root or end at a leaf, but it must go downward: from a node to one of its children, then to one of that child's children, and so on. A single node is a path too.

Examples

Example 1

Input: root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], targetSum = 8

Output: 3

Explanation: Three paths add up to 8: 5 → 3, 5 → 2 → 1 and −3 → 11. A path can start and end anywhere, as long as it goes down.

Example 2

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

Output: 3

Explanation: 5 → 4 → 11 → 2, 5 → 8 → 4 → 5 and 4 → 11 → 7.

Example 3

Input: root = [0, 0, 0], targetSum = 0

Output: 5

Explanation: All five downward paths add up to 0: each node alone, and the root with either child.

Constraints

  • The number of nodes in the tree is in the range [0, 1000].
  • −10^9 ≤ Node.val ≤ 10^9
  • −1000 ≤ targetSum ≤ 1000

Editorial

Brute Force

Intuition

Every path starts at some node and goes down. So make every node a start: from it, walk every way down, adding the values as you go, and count each time the sum equals targetSum. Don't stop at a hit: values can be zero or negative, so a longer path can hit the target again.

Step-by-Step Explanation

Let's trace root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], targetSum = 8:

  1. From 10, no way down reaches 8.
  2. From 5, 2 paths reach 8: 5 → 3 and 5 → 2 → 1. That makes 2.
  3. From 3 under 5, no way down reaches 8.
  4. From 3 under 3, no way down reaches 8.
  5. From -2, no way down reaches 8.
  6. From 2, no way down reaches 8.
  7. From 1, no way down reaches 8.
  8. From -3, 1 path reaches 8: -3 → 11. That makes 3.
  9. From 11, no way down reaches 8.

A Walk Down from Every Node — Indigo is the start; green, the paths from it that reach the target.

Algorithm

  1. down(node, total): add node.val to total, count 1 if it equals targetSum, and add what down finds in both children.
  2. Call down(start, 0) for every node start in the tree, and add up the counts.

Code

A path of 1,000 values of 10^9 sums to 10^12, so C++ and Java keep the sum in 64 bits.

class Solution {
    // every path from one start: each way down, counting the sums that reach the target
    int down(TreeNode* node, long long total, int target) {
        if (node == nullptr) return 0;
        total += node->val;               // 64 bits: a path of 1,000 values can reach 10^12
        return (total == target) + down(node->left, total, target) + down(node->right, total, target);
    }

public:
    int pathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return 0;    // every node is a start
        return down(root, 0, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
    }
};

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        def down(node, total):            # every path from one start: each way down
            if node is None:
                return 0
            total += node.val
            return (total == targetSum) + down(node.left, total) + down(node.right, total)

        def every(node):                  # every node is a start
            if node is None:
                return 0
            return down(node, 0) + every(node.left) + every(node.right)

        return every(root)

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;       // every node is a start
        return down(root, 0, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }

    // every path from one start: each way down, counting the sums that reach the target
    private int down(TreeNode node, long total, int target) {
        if (node == null) return 0;
        total += node.val;                // 64 bits: a path of 1,000 values can reach 10^12
        return (total == target ? 1 : 0) + down(node.left, total, target) + down(node.right, total, target);
    }
}

var pathSum = function(root, targetSum) {
    const down = (node, total) => {       // every path from one start: each way down
        if (node === null) return 0;
        total += node.val;
        return (total === targetSum ? 1 : 0) + down(node.left, total) + down(node.right, total);
    };
    const every = (node) => {             // every node is a start
        if (node === null) return 0;
        return down(node, 0) + every(node.left) + every(node.right);
    };
    return every(root);
};

Complexity Analysis

Time Complexity: O(n · h)

Each node is added once for every node above it, h of them at most: O(n log n) on a balanced tree, O(n²) on a tree that's one long chain.

Space Complexity: O(h)

The two recursions, each as deep as the tree.

Why This Approach Is Not Efficient

It passes here, in every language: with at most 1,000 nodes, even a chain is only about half a million additions. But it repeats itself. On the deepest tree the tests use, a chain of 1,000 nodes (with 11,639 paths that sum to the target), it took 173.3 ms in Python, against 0.67 ms for the running sums below.

The repeated work is the sums: every start adds up the same nodes below it again. Add each value once instead, on the way down from the root, and keep the running sum. A path from node a down to node b sums to the running sum at b minus the running sum just above a. So a path ending at b hits the target exactly when some running sum earlier on the same path equals running - targetSum, and a count of the running sums on the path answers that in one lookup.

Optimal Approach - Running Sums on the Path

Intuition

Walk down from the root keeping the running sum, and a count of every running sum on the path from the root to the current node, starting with 0 once for the empty path above the root:

  • At each node: add its value to the running sum. The paths that end here are the earlier running sums equal to running - targetSum, so add their count.
  • Going down: count the node's own running sum, then visit both children.
  • Coming back up: take that count away again. The counts must describe one path, from the root to where the walk is, or a branch would see sums from another branch.

Step-by-Step Explanation

Let's trace root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], targetSum = 8:

  1. At 10 the running sum is 10. No earlier sum on this path is 10 - 8, 2, so no path ends here.
  2. At 5 the running sum is 15. No earlier sum on this path is 15 - 8, 7, so no path ends here.
  3. At 3 the running sum is 18. 18 - 8 is 10, and that sum appears earlier on the path, so the nodes after it, 5, 3, sum to 8. That's path 1.
  4. At 3 the running sum is 21. No earlier sum on this path is 21 - 8, 13, so no path ends here.
  5. At -2 the running sum is 16. No earlier sum on this path is 16 - 8, 8, so no path ends here.
  6. At 2 the running sum is 17. No earlier sum on this path is 17 - 8, 9, so no path ends here.
  7. At 1 the running sum is 18. 18 - 8 is 10, and that sum appears earlier on the path, so the nodes after it, 5, 2, 1, sum to 8. That's path 2.
  8. At -3 the running sum is 7. No earlier sum on this path is 7 - 8, -1, so no path ends here.
  9. At 11 the running sum is 18. 18 - 8 is 10, and that sum appears earlier on the path, so the nodes after it, -3, 11, sum to 8. That's path 3.

Running Sums on the Path — Indigo is the node being visited; amber, the path above it; green, a path found. Under the tree, the running sums on the path.

Algorithm

  1. Start with sums = {0: 1} and call go(root, 0).
  2. go(node, running): if node is empty, return 0. Add node.val to running. Set found to sums[running - targetSum] (0 if it's absent), add 1 to sums[running], add what both children find, then take the 1 away from sums[running] and return found.

Code

C++ and Java keep the running sums in 64 bits, for the same reason as above.

class Solution {
    unordered_map<long long, int> sums;   // the running sums on the path from the root, counted
    long long target;

    int go(TreeNode* node, long long running) {
        if (node == nullptr) return 0;
        running += node->val;             // 64 bits: a path of 1,000 values can reach 10^12
        int found = 0;
        auto it = sums.find(running - target);   // paths ending here start just below an earlier prefix
        if (it != sums.end()) found = it->second;
        sums[running]++;
        found += go(node->left, running) + go(node->right, running);
        sums[running]--;                  // leaving this node: its sum is no longer on the path
        return found;
    }

public:
    int pathSum(TreeNode* root, int targetSum) {
        target = targetSum;
        sums[0] = 1;                      // the empty prefix
        return go(root, 0);
    }
};

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        sums = {0: 1}                     # the running sums on the path from the root, counted; the empty one too

        def go(node, running):
            if node is None:
                return 0
            running += node.val
            found = sums.get(running - targetSum, 0)   # paths ending here start just below an earlier prefix
            sums[running] = sums.get(running, 0) + 1
            found += go(node.left, running) + go(node.right, running)
            sums[running] -= 1            # leaving this node: its sum is no longer on the path
            return found

        return go(root, 0)

class Solution {
    private final Map<Long, Integer> sums = new HashMap<>();   // the running sums on the path from the root, counted
    private long target;

    public int pathSum(TreeNode root, int targetSum) {
        target = targetSum;
        sums.put(0L, 1);                                        // the empty prefix
        return go(root, 0);
    }

    private int go(TreeNode node, long running) {
        if (node == null) return 0;
        running += node.val;                                    // 64 bits: a path of 1,000 values can reach 10^12
        int found = sums.getOrDefault(running - target, 0);     // paths ending here start just below an earlier prefix
        sums.merge(running, 1, Integer::sum);
        found += go(node.left, running) + go(node.right, running);
        sums.merge(running, -1, Integer::sum);                  // leaving this node: its sum is no longer on the path
        return found;
    }
}

var pathSum = function(root, targetSum) {
    const sums = new Map([[0, 1]]);       // the running sums on the path from the root, counted; the empty one too
    const go = (node, running) => {
        if (node === null) return 0;
        running += node.val;
        let found = sums.get(running - targetSum) || 0;   // paths ending here start just below an earlier prefix
        sums.set(running, (sums.get(running) || 0) + 1);
        found += go(node.left, running) + go(node.right, running);
        sums.set(running, sums.get(running) - 1);         // leaving this node: its sum is no longer on the path
        return found;
    };
    return go(root, 0);
};

Complexity Analysis

Time Complexity: O(n)

Each node is visited once, with one lookup and two updates in a hash map.

Space Complexity: O(h)

The map holds at most the h + 1 running sums on one path, and the recursion is h deep.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Counting only the paths from the root. return (total == targetSum) + go(node.left, total) + go(node.right, total)

On root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], targetSum = 8 it returns 0; the answer is 3. A path can start at any node, not just the root. Counting the root paths alone misses every path that starts lower down, like 5 → 3 in the first example.

Never taking a sum back off. return found + go(node.left, running) + go(node.right, running)

On root = [1, 2, 5], targetSum = 3 it returns 2; the answer is 1. The counts must describe the path from the root to the current node and nothing else. Without the decrement on the way back up, sums from a finished left branch are still counted when the walk is in the right one, and a path that jumps between branches gets counted.

A running sum that wraps around. running = wrap(running + node.val)

On root = [1000000000, 1000000000, null, 1000000000, null, 1000000000, null, 294967296], targetSum = 0 it returns 1; the answer is 0. Values go up to 10^9 and a path can hold 1,000 of them, so a running sum can reach 10^12. In 32 bits it wraps around, and a path summing to 2^32 more than the target looks like a hit. C++ and Java need a 64-bit running sum (this one copies an int's wrap-around in Python).

Where This Pattern Is Taught

This problem practises state passed down a tree, with prefix sums. It's taught in Recursion on Trees: Heights, Paths and Return Values, which steps through this example and measures the walk from every node against the running sums.