Path Sum I, II & III

Three questions with the same name and a growing difficulty. They share one lesson because each one builds on the last:

Path Sum (I) — given root and targetSum, is there a root-to-leaf path whose values add up to targetSum? Return true or false.
Path Sum II — return every root-to-leaf path that adds up to targetSum, as lists of values.
Path Sum III — count the paths that add up to targetSum, where a path may start and end anywhere, as long as it goes downward (parent to child).

The tree 5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1 with target 22. Two root-to-leaf paths add up to 22: 5, 4, 11, 2 and 5, 8, 4, 5. So Path Sum I answers true and Path Sum II returns both paths.

Example

root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1],  targetSum = 22
Path Sum I   -> true
Path Sum II  -> [[5, 4, 11, 2], [5, 8, 4, 5]]

root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1],  targetSum = 8
Path Sum III -> 3      (5 -> 3,  5 -> 2 -> 1,  -3 -> 11)

The key idea for I and II: instead of adding values up and comparing at the end, carry the remaining amount down. Each node subtracts its value; a leaf that receives exactly 0 remaining finishes a matching path. (Values can be negative, so you can't stop early just because the sum got big.)

Free account

Keep reading. It's free.

Sign up to read the rest of this lesson: 8 more sections, 3 drawings, 2 dry-run simulators and code in JavaScript, Python, Java and C++.

Still to come

Path Sum I — 1. Brute force: list every root-to-leaf sum
Path Sum I — 2. Best solution: carry what's remaining, stop at the first match
Path Sum II: collect the paths with backtracking
Path Sum III — 1. Brute force: start a search at every node
Path Sum III — 2. Best solution: prefix sums on the current path
Comparing the approaches
Edge cases to test
Variations

Prev Next

Mark completed

Was this helpful?

Path Sum I, II & III

Example

Keep reading. It's free.

Keep exploring