Understanding and Solving “Path Sum III”: Coding Interview Question

In this post, we’re delving deep into a tree-based problem from LeetCode.

Problem Statement

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Solution

Brute Force Approach

We can approach this problem using a recursive, depth-first traversal. At each node, we’ll check:

1. How many paths have a sum ending at the current node.
2. How many paths have a sum starting from the left child.
3. How many paths have a sum starting from the right child.

By summing up these counts, we get our answer!

Java Solution

public class Solution {

    public int pathSum(TreeNode root, int sum) {
        // Base condition
        if (root == null) return 0;

        // Convert the sum to long to handle large values
        long longSum = (long) sum;

        // Check paths from current node, then move left and right
        return pathsFrom(root, longSum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }

    private int pathsFrom(TreeNode node, long sum) {
        // Base condition
        if (node == null) return 0;

        // Convert the node value to long to handle large values
        long longVal = (long) node.val;

        // If current node's value is the sum, that's one path right there!
        // Then, keep looking for more paths down this branch that make up the sum
        return (longVal == sum ? 1 : 0) + pathsFrom(node.left, sum - longVal) + pathsFrom(node.right, sum - longVal);
    }
}

Time and Space Complexity

The time complexity of this solution is O(n^2) in the worst case, where nn is the number of nodes. This is because for each node, in the worst scenario, we could end up traversing all the other nodes beneath it.

The space complexity is O(n) due to the recursive stack, which in the worst-case scenario of a skewed tree can go up to nn levels deep.

However, in balanced trees, our solution will run faster than this worst-case scenario and will have a space complexity of O(log⁡n) due to the height of a balanced tree being log⁡nlogn.

Optimized Approach

We can optimize this using a concept called the prefix sum.

The idea behind prefix sum is simple: as we traverse the tree, for each node, we accumulate the sum from the root to that node. If we maintain this running sum in a hashmap and at any node the running sum minus target sum equals a value that exists in our hashmap, it means there are paths (as many as the count of that value in the hashmap) that would sum up to our target value.

public class Solution {
    public int pathSum(TreeNode root, int sum) {
        // The map to store prefix sum (in long) and its occurrences
        Map<Long, Integer> prefixSumMap = new HashMap<>();
        
        // Initialize with base sum 0 and its occurrence as 1
        prefixSumMap.put(0L, 1);
        
        return helper(root, 0L, sum, prefixSumMap);
    }
    
    private int helper(TreeNode node, long currentSum, int targetSum, Map<Long, Integer> prefixSumMap) {
        if (node == null) return 0;
        
        // Update the current sum
        currentSum += node.val;
        
        // Check how many paths have a sum equal to (currentSum - targetSum)
        int numOfPaths = prefixSumMap.getOrDefault(currentSum - targetSum, 0);
        
        // Update the prefixSumMap with currentSum
        prefixSumMap.put(currentSum, prefixSumMap.getOrDefault(currentSum, 0) + 1);

        // Recurse on left and right subtrees
        numOfPaths += helper(node.left, currentSum, targetSum, prefixSumMap);
        numOfPaths += helper(node.right, currentSum, targetSum, prefixSumMap);
        
        // Decrement the current sum's count (backtrack)
        prefixSumMap.put(currentSum, prefixSumMap.get(currentSum) - 1);
        
        return numOfPaths;
    }
}

Time and Space Complexity:

Time Complexity: O(n), where n is the number of nodes. We traverse each node once.

Space Complexity: O(n) in the worst case. This is because of the hashmap and the recursive call stack. On a balanced tree, the height (and therefore the maximum number of recursive calls on the stack) would be O(log n), but the hashmap could still store up to n different sums.

This approach is a significant improvement from the initial solution, especially in terms of time complexity. The optimization revolves around the insight that instead of repeatedly calculating sums for every path, we can use the prefix sums to quickly identify how many paths end at our current node with the desired sum.

Follow me on Medium if you found this post helpful.