Path Sum III

Medium Trees & BST Backtracking Original on LeetCode

Reported atCREDZepto

Path Sum III is a medium trees & bst problem solved with the backtracking pattern. The best approach, optimal (prefix sums on the current path), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (start a walk at every node) up.

Problem

Given the root of a binary tree and an integer targetSum, count the paths whose node values add up to targetSum.

A path may start and end at any nodes, but it must go downward only, from a parent to one of its children at each step. A single node is also a path.

Examples

Example 1

Input
root = [4,2,6,-3,null,0,1], targetSum = 6
Output
3
Why
The paths 4 → 2, the single node 6, and 6 → 0 each add up to 6.

Example 2

Input
root = [1,-1,1,null,2], targetSum = 1
Output
3
Why
The root on its own, the right child on its own, and -1 → 2 each sum to 1. The path 1 → -1 → 2 sums to 2 and does not count.

Example 3

Input
root = [], targetSum = 0
Output
0
Why
An empty tree has no paths at all.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (start a walk at every node)O(n · h), O(n²) worst caseO(h)
Optimal (prefix sums on the current path)O(n)O(n)

1Brute force (start a walk at every node)

TimeO(n · h), O(n²) worst caseEach node starts a walk over its subtree; a node is visited once per ancestor, so n · h in total.
SpaceO(h)Recursion depth equals the tree height h.

Treat every node as the top of a path. From it, walk down every branch keeping a running sum and count the nodes where the sum equals the target. Do this for all nodes.

  1. pathSum(node) = countFrom(node, 0) + pathSum(node.left) + pathSum(node.right), with 0 for an empty tree.
  2. countFrom(node, sum): sum += node.val; result = (sum == target ? 1 : 0) + countFrom(left, sum) + countFrom(right, sum).
  3. Use 64-bit sums.
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        return countFrom(root, 0L, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }

    private int countFrom(TreeNode node, long sum, int target) {
        if (node == null) return 0;
        sum += node.val;
        return (sum == target ? 1 : 0) + countFrom(node.left, sum, target) + countFrom(node.right, sum, target);
    }
}

2Optimal (prefix sums on the current path)

TimeO(n)Every node is visited once with O(1) average hash-map work.
SpaceO(n)The map holds at most h prefixes at a time, and the recursion is h deep; h can be n.

Walk the tree once with DFS, carrying the prefix sum from the root to the current node. A downward path ending here sums to the target exactly when some ancestor's prefix equals prefix - target. A hash map counts the prefixes on the current root-to-node chain (seeded with 0 for the empty prefix). After finishing a node's children, decrement its prefix so sibling branches never see it.

  1. counts = {0: 1}.
  2. dfs(node, prefix): prefix += node.val; result = counts[prefix - target].
  3. counts[prefix]++, add dfs(left) and dfs(right), then counts[prefix]--.
  4. Return dfs(root, 0) (0 for an empty tree). Use 64-bit prefix sums.
class Solution {
    private final Map<Long, Integer> counts = new HashMap<>();

    public int pathSum(TreeNode root, int targetSum) {
        counts.clear();
        counts.put(0L, 1);
        return dfs(root, 0L, targetSum);
    }

    private int dfs(TreeNode node, long prefix, int target) {
        if (node == null) return 0;
        prefix += node.val;
        int result = counts.getOrDefault(prefix - target, 0);
        counts.merge(prefix, 1, Integer::sum);
        result += dfs(node.left, prefix, target) + dfs(node.right, prefix, target);
        counts.merge(prefix, -1, Integer::sum);
        return result;
    }
}

Edge cases to test

  • An empty tree (answer 0)
  • Negative values, so a path can reach the target, go past it and come back
  • Path sums that overflow a 32-bit integer
  • Zero-valued nodes, which make several overlapping paths share the same sum

Hints

Hint 1

A path is fixed by its top node and its bottom node. Try every top node and walk down from it.

Hint 2

Along one root-to-node chain, a path ending at the current node has sum = prefix(current) - prefix(some ancestor).

Hint 3

Keep a hash map of how many times each prefix sum occurs on the current chain; remove the current prefix when you return from a node.

FAQ

What is the best time complexity for Path Sum III?

Optimal (prefix sums on the current path) runs in O(n) time and O(n) extra space. Every node is visited once with O(1) average hash-map work.

Which pattern does Path Sum III use?

It is a trees & bst problem that uses the backtracking pattern. Other problems with the same pattern: Root to Leaf Paths, Path Sum II.

Is there a brute force solution for Path Sum III?

Yes. Brute force (start a walk at every node) takes O(n · h), O(n²) worst case time and O(h) space. Treat every node as the top of a path.

Which edge cases should I test for Path Sum III?

An empty tree (answer 0); Negative values, so a path can reach the target, go past it and come back; Path sums that overflow a 32-bit integer; Zero-valued nodes, which make several overlapping paths share the same sum.