Count Downward Stretches With a Given Total
Solve this ProblemYou are given the root of a binary tree and an integer target. A stretch is a chain of nodes that goes strictly downward: each node after the first is a child of the node before it. A stretch may start and end at any node — it does not have to include the root or end at a leaf. Return the number of stretches whose values add up to exactly target.
Trying every node as a starting point works but repeats a lot of walking. Prefix sums along the current root-to-node path let you count all stretches that end at a node with a single lookup.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100 - ◆
−100 ≤ node.val ≤ 100; −1000 ≤ target ≤ 1000 - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
A stretch is a chain of nodes that goes strictly downward (each next node is a child of the one before). It may start and end at ANY nodes — it need not touch the root or a leaf. Return how many stretches have values adding up to exactly target
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Start a Downward Count at Every Node
BruteEvery stretch begins at some node, so treat each node as a starting point. A helper walks downward from a start node keeping a "remaining" amount: each visited node that equals the remaining amount means the stretch ending there totals the target, so count one; then continue into both children with the remaining amount reduced by the node's value (a stretch may keep going past a match, because later negative values can bring the total back). Finally, repeat with the left and right children as new starting points. Each of the n nodes starts a walk of up to O(h) depth-steps per branch: O(n · h) time — O(n²) on a long chain.
O(n · h)O(h)1class Solution {
2 public int countStretches(TreeNode root, int target) {
3 if (root == null) return 0;
4 return startingAt(root, target) + countStretches(root.left, target) + countStretches(root.right, target);
5 }
6
7 private int startingAt(TreeNode node, int remaining) {
8 if (node == null) return 0;
9 int here = node.val == remaining ? 1 : 0;
10 return here + startingAt(node.left, remaining - node.val) + startingAt(node.right, remaining - node.val);
11 }
12}Optimal — Prefix Sums With a Counting Map
OptimalTrack the running sum from the root down to the current node. A stretch that ends at this node and starts just below some ancestor has total running − (the running sum at that ancestor). So the stretch totals target exactly when an ancestor's running sum equals running − target. Keep a map from "running sum" to "how many ancestors on the current path have it", seeded with {0: 1} so that stretches starting at the root are counted. At each node: add the number of ancestors with running − target, record this running sum, recurse into both children, and finally remove this running sum again (backtrack) so siblings only see their own ancestors. Every node is handled once: O(n) time and O(h) map size. (The C version replaces the map with a direct-address array, since all sums lie within ±10 000.)
O(n)O(h)1class Solution {
2 public int countStretches(TreeNode root, int target) {
3 Map<Integer, Integer> seen = new HashMap<>();
4 seen.put(0, 1);
5 return walk(root, 0, target, seen);
6 }
7
8 private int walk(TreeNode node, int running, int target, Map<Integer, Integer> seen) {
9 if (node == null) return 0;
10 running += node.val;
11 int found = seen.getOrDefault(running - target, 0);
12 seen.merge(running, 1, Integer::sum);
13 found += walk(node.left, running, target, seen);
14 found += walk(node.right, running, target, seen);
15 seen.merge(running, -1, Integer::sum);
16 return found;
17 }
18}