Downward Segments With Target Sum
MediumTrees
Problem
A downward segment is a path that starts at any node and moves only from parent to child, ending at any node at or below its start (a single node is a segment).
Given the root of a binary tree and an integer target, return how many downward segments have values summing to target.
Example 1
- Input:
- root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], target = 8
- Output:
- 3
5 → 3, 5 → 2 → 1 and -3 → 11.
Example 2
- Input:
- root = [0, 0, 0], target = 0
- Output:
- 5
Each of the three nodes alone, plus root → left and root → right.
Constraints
- 0 ≤ number of nodes ≤ 1023
- Tree height ≤ 500
- -10^9 ≤ node.val ≤ 10^9
- -1000 ≤ target ≤ 1000
Hint
Show the first hint
On a single root-to-node path, a segment ending at the current node is a difference of two prefix sums.
Walkthrough
How to approach it
01Clarify before coding
- Can a segment go up and then down? No, strictly parent to child.
- Does a single node count? Yes, when its value equals target.
- Can values be negative? Yes, so a sliding-window shortcut does not work.
02Brute force
From every node, walk down every descendant path while summing, counting matches.
Cost: O(n · h): O(n log n) on balanced trees but O(n²) on a chain.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.