Cracking The Coding Interview Together – Problem 4.12: Paths with Sum

Imagine you are reviewing a pull request for a financial ledger system. The system models transaction hierarchies as a tree structure, and the task is to find all sub-hierarchies (paths) that sum up to a specific target value. The author of the PR has submitted a solution that works, but as you look closer, you notice a nested traversal pattern. For every single node in the tree, they are launching a brand-new depth-first search (DFS) to find matching paths. On a production dataset with millions of transactions, this O(N log N) or worse, O(N^2) approach will grind your servers to a halt.

This is the exact technical challenge presented in Cracking the Coding Interview, Problem 4.12: Paths with Sum. It is a classic problem that separates junior developers who rely on brute-force recursion from senior engineers who understand how to optimize state management across recursive call stacks. Today, we are going to tackle this problem together. Our goal is to design, implement, and analyze an optimal, production-ready O(N) time complexity solution using prefix sums and backtracking.

Problem Statement

Paths with Sum: You are given a binary tree in which each node contains an integer value (which might be positive or negative). Design an algorithm to count the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The problem asks us to write an algorithm to count the number of paths in a binary tree that sum to a given target value. Each node in the tree contains an integer value, which can be positive, negative, or zero. The path does not need to start at the root or end at a leaf, but it must go downwards—meaning it can only travel from parent nodes to child nodes.

Our operational goals are:

• Correctness: Accurately count all valid downward paths, handling negative numbers and zeros correctly.
• Efficiency: Avoid redundant traversals. We want to visit each node exactly once, achieving O(N) time complexity.
• Memory Safety: Keep the space complexity proportional to the height of the tree, O(H), to prevent stack overflow errors on deep trees.

Analyze the Problem Together

Let's break down the constraints and the "Aha!" moment that leads to the optimal solution. If we look at a naive approach, we might think: "For every node, let's find all paths starting from this node that sum to the target. Then, we recursively call this same function on the left and right children."

Let's compare the naive approach with our optimized approach:

The "Aha!" moment comes from a well-known array technique: Prefix Sums. If you have an array, and you want to find sub-arrays that sum to T, you can keep a running sum as you iterate. If the running sum at index j is S_j, and we want to find a sub-array ending at j that sums to T, we are looking for a previous index i (where i < j) such that S_j - S_i = T. Rearranging this, we get S_i = S_j - T. By storing our historical prefix sums in a hash map, we can look up the frequency of S_i in O(1) time.

Can we apply this to a binary tree? Absolutely! A path from the root down to any node is just like an array. As we traverse down a branch, we can maintain a running sum and store it in a hash map. But here is the catch—the "Aha!" conflict: unlike a linear array, a tree branches. When we finish exploring a node's left subtree and move to its right subtree, the prefix sums from the left subtree are no longer valid because they are not on the path from the root to the right subtree. If we don't clean up our hash map, we will pollute our search space with invalid paths from sibling branches.

This is where backtracking becomes essential. As we unwind our recursive call stack, we must decrement the frequency of the current node's prefix sum from our hash map. This ensures that the map only ever contains prefix sums from the path directly above the current node.

Questions for the Interviewer

Before writing a single line of code, a senior engineer always clarifies the boundaries of the problem. Here are the questions we should ask:

• Q1: Can the node values or the target sum be extremely large?
  Why it matters: If the sum of values exceeds the limits of a standard 32-bit integer, we need to use 64-bit integers (e.g., long in Java) to prevent integer overflow bugs.
• Q2: How should we handle empty trees or null nodes?
  Why it matters: We must establish clean base cases to prevent NullPointerExceptions.
• Q3: Are we allowed to modify the tree structure?
  Why it matters: Some destructive algorithms modify node values to store state. In a production environment, read-only operations are highly preferred for thread safety and concurrency. We will design a non-destructive solution.

Think About the Solution

Let's design our high-level architecture. We will implement a recursive helper function that performs a pre-order traversal (Root, Left, Right) of the tree. We will pass along three key pieces of state:

1. The current TreeNode.
2. The runningSum accumulated from the root down to the current node.
3. A Map<Long, Integer> that tracks the frequencies of all prefix sums seen along the current active path.

At each node, we will:

• Update the runningSum by adding the current node's value.
• Check if runningSum - targetSum exists in our map. If it does, we add its frequency to our total path count.
• Add the new runningSum to our map (incrementing its count).
• Recurse into the left and right children.
• Backtrack: Decrement the count of the current runningSum in the map before returning. If the count drops to zero, we remove the key entirely to save space.

An important edge case: What if a path starting directly from the root sums to the target? In this case, runningSum - targetSum = 0. To handle this seamlessly without adding complex conditional logic, we pre-populate our hash map with a default entry: {0: 1}. This represents an empty path with a sum of 0 seen exactly once.

Write Code and Explain

Here is the complete, production-ready Java implementation of our optimized algorithm:

import java.util.HashMap;
import java.util.Map;

public class PathSumSolver {

    // Definition for a binary tree node.
    public static class TreeNode { 
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) { 
            this.val = val;
        }
    }

    /**
     * Counts the number of downward paths that sum to the target value.
     * 
     * @param root The root of the binary tree.
     * @param targetSum The target sum we are searching for.
     * @return The total number of matching paths.
     */
    public int countPathsWithSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        
        // Map to store prefix sums and their frequencies along the current path.
        // We use Long to prevent integer overflow during summation.
        Map<Long, Integer> prefixSumCounts = new HashMap<>();
        
        // Base case: A prefix sum of 0 has been seen once (representing an empty path starting at the root).
        prefixSumCounts.put(0L, 1);
        
        return countPaths(root, 0L, targetSum, prefixSumCounts);
    }

    private int countPaths(TreeNode node, long runningSum, int targetSum, Map<Long, Integer> prefixSumCounts) {
        if (node == null) {
            return 0;
        }

        // 1. Update the running sum
        runningSum += node.val;

        // 2. Determine if there is a matching sub-path ending at this node
        long sumToFind = runningSum - targetSum;
        int totalPaths = prefixSumCounts.getOrDefault(sumToFind, 0);

        // 3. Add the current running sum to the map to make it available for child nodes
        prefixSumCounts.put(runningSum, prefixSumCounts.getOrDefault(runningSum, 0) + 1);

        // 4. Recurse down to the left and right subtrees
        totalPaths += countPaths(node.left, runningSum, targetSum, prefixSumCounts);
        totalPaths += countPaths(node.right, runningSum, targetSum, prefixSumCounts);

        // 5. Backtrack: Remove the current running sum from the map before returning up the call stack
        int currentCount = prefixSumCounts.get(runningSum);
        if (currentCount == 1) {
            prefixSumCounts.remove(runningSum);
        } else {
            prefixSumCounts.put(runningSum, currentCount - 1);
        }

        return totalPaths;
    }
}

Step-by-Step Walkthrough

Let's trace this code with a simple example. Suppose we have a tree where the root is 10, its left child is 5, and the target sum is 15.

1. We initialize prefixSumCounts with {0: 1}.
2. We call countPaths on the root node (10) with a runningSum of 0.
3. At node 10, runningSum becomes 10. We check if runningSum - targetSum (which is 10 - 15 = -5) is in the map. It is not. We add 10 to our map: {0: 1, 10: 1}.
4. We recurse to the left child (5).
5. At node 5, runningSum becomes 15. We check if runningSum - targetSum (which is 15 - 15 = 0) is in the map. Yes! 0 is in the map with a count of 1. We add 1 to our totalPaths.
6. We add 15 to our map: {0: 1, 10: 1, 15: 1}.
7. Since node 5 has no children, we prepare to return. Before returning, we backtrack: we decrement the count of 15 in our map, removing it. The map returns to {0: 1, 10: 1}.
8. We return up to node 10, and then backtrack node 10, leaving the map as {0: 1}. The final count returned is 1.

Time & Space Complexity

Let's analyze the efficiency of our solution rigorously:

• Time Complexity: O(N)
  We visit each node in the binary tree exactly once. At each node, we perform basic arithmetic operations and hash map lookups/updates. Since hash map operations run in O(1) average time, the overall time complexity is strictly linear, O(N), where N is the number of nodes in the tree.
• Space Complexity: O(H)
  The space complexity is determined by two factors: the recursion call stack and the size of the hash map. Both are bounded by the maximum depth of the tree, O(H), where H is the height of the tree. In the worst-case scenario of a completely skewed tree (essentially a linked list), the space complexity will be O(N). In a balanced tree, it will be O(log N). This is highly optimal as we do not store state for nodes outside our current active path.

Why This Problem Matters (The Senior Perspective)

As a senior engineer, you should look beyond the immediate coding puzzle and see the broader architectural patterns at play here. This problem highlights three critical software engineering concepts:

1. The Transactional Ledger Pattern

In financial systems, auditing historical balances or finding specific transaction sequences is a common requirement. The prefix sum technique we used here is identical to how we analyze streaming ledger data to find specific transaction windows without re-scanning the entire database. It is the difference between an application that scales linearly and one that crashes under load.

2. State Management and Backtracking

When writing recursive algorithms, managing shared state (like our hash map) is a common source of bugs. Passing a single map instance down the call stack is highly efficient because it avoids copying data. However, it introduces side effects. The backtracking step is a clean, deterministic way to manage this shared state without the overhead of object allocation. It is a pattern you will use constantly in compiler design, parsing, and routing engines.

3. Thread Safety and Immutability

Our solution is non-destructive; it does not alter the tree structure or the node values. In a multi-threaded production environment, this is incredibly valuable. Multiple threads can safely run this path-counting algorithm concurrently on the same tree structure without needing complex synchronization locks, ensuring high throughput.

Final Thoughts

We started with a naive, nested traversal that would have choked on production-scale data, and together, we designed an elegant, linear-time solution using prefix sums and backtracking. We also ensured our code was robust against integer overflows and memory leaks.

The next time you face a tree traversal problem, ask yourself: "Can I carry historical state down the stack, and clean it up on the way back up?" Master this pattern, and you will write code that is not only correct but highly performant.

What are your thoughts on this approach? Have you used prefix sums to optimize other hierarchical data structures? Let's discuss in the comments below!

Until next time, happy coding!