Tree Path Sum Problems in Java: DFS and BFS Solutions

Tree path sum problems represent a fundamental category of binary tree algorithms where we must determine if paths exist from root to leaf nodes with specific sum constraints, requiring careful traversal and backtracking strategies for optimal solutions.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are we looking for paths from root to leaf, or any path in the tree?
2. Can the input tree be modified during the solution process?
3. What is the expected return format - just a boolean, or do we need to return the actual path(s)?
4. Are duplicate values allowed in the tree, and how should we handle them?
5. What is the target time complexity for follow-ups - O(n) or better?

Restate the pattern or problem type in your own words: This is a classic tree traversal pattern where we need to find paths that sum to a target value. The problem typically involves traversing a binary tree and identifying all root-to-leaf paths (or any paths) where the sum of node values equals a given target. This pattern requires combining tree traversal with path tracking and sum calculation.

Clarify the signal words and constraint shape that point to it:

• "Sum of path" or "path sum" - direct signal words
• "Root to leaf" - indicates we're looking for complete paths from root to end nodes
• "Target sum" - suggests we're filtering paths based on a specific value
• "All paths" or "any path" - indicates we're collecting results rather than just checking existence

Note any assumptions you are making:

• The tree is a binary tree (not n-ary)
• We're typically looking for root-to-leaf paths, though the problem can be adapted to any path
• Node values can be negative (which makes this more complex than just positive numbers)
• The target sum is a fixed value we're comparing against

Identify whether the pattern is best suited for static, streaming, or online scenarios if relevant: This pattern is primarily designed for static tree structures where we can traverse the entire structure. It's not naturally suited for streaming data since we need to know the complete tree structure to find all paths. However, it can be adapted for online scenarios where we're checking if a path sum exists as new nodes are added to the tree.

2. When to Use This Pattern

Signal words and constraint shapes:

• "Path sum," "root-to-leaf," "target sum" - direct indicators
• "Binary tree" or "tree" structure with nodes containing values
• "Sum to target" or "find path with sum" - mathematical constraint
• "All paths" or "any path" - completeness requirement

Why this pattern fits better than alternatives: This pattern is specifically designed for tree traversal problems where we need to track cumulative values along paths from root to leaves. Unlike array-based sliding window or two-pointer approaches, tree path sum problems require maintaining state across hierarchical structures. The key advantage is that we can leverage the tree's recursive structure to naturally maintain path sums, avoiding complex state management.

Conditions where variations apply:

• If the problem asks for "path" that can start and end anywhere in the tree (not necessarily root-to-leaf), we'd use a different approach like hash map + prefix sums
• For "maximum sum path" in binary trees, we'd use a variation that tracks global maximum rather than just checking against target
• If the tree is not binary or has more than 2 children, we'd adapt the traversal accordingly

Core insight: The key insight is that we can use recursive backtracking to maintain a running sum from root to current node, and at each leaf we check if that sum equals our target. This naturally handles the path constraint by construction - we're always working with a single path from root to leaf, and we can easily track the cumulative sum at each node.

The pattern works particularly well because:

1. Tree structure naturally supports hierarchical accumulation
2. We can use DFS traversal to explore all root-to-leaf paths systematically
3. Path sum constraints can be checked at leaf nodes with O(1) validation
4. The recursive structure makes it easy to maintain and backtrack path state

3. Approach Evolution

Interview communication script:

My first instinct is to use a brute force approach where I check every possible path from root to leaf, but that's O(n²) because for each node I might have to traverse all paths. Let me think about how to optimize this - I notice that if I maintain a running sum from root to current node, I can reduce it to O(n) by using DFS traversal. The key insight is that for any path from root to leaf, I only need to track the sum from root to current node, and check if any prefix of that path equals the target.

Let me think about this more carefully. If I'm at any node and I know the sum from root to that node, then if there exists a prefix path such that (current_sum - prefix_sum) = targetSum, I've found a valid subpath. This suggests using a HashMap to store prefix sums.

Actually, let me reconsider - this is more nuanced than just prefix sums. The problem asks for paths that sum to target, where a path goes from parent to child, not necessarily from root. So I need to track all prefix sums from root down to current node and check if any difference equals target sum.

The brute force approach would be to for each node, traverse all paths from that node downward and check if any sum equals target. But that's inefficient because we're recomputing sums repeatedly.

The optimized approach uses a HashMap to store prefix sums from root to current node. At each node, I compute the current cumulative sum and check if (current_sum - target) exists in my map. If it does, that means there are paths ending at current node with sum equal to target.

The key optimization is maintaining a prefix sum map that allows O(1) lookup of previous sums, reducing the overall time complexity from O(n²) to O(n).

Brute-force approach and why it is not ideal: The brute force approach would involve checking every possible path from every node to every leaf. For each node, we'd compute all path sums ending at that node by traversing downward. This results in O(n²) time complexity because for each of the n nodes, we might traverse down to all leaf nodes in worst case.

Improved approach and the key optimization: The improved approach uses a HashMap to store prefix sums from root to current node. At each node, we compute the cumulative sum from root to that node and check if (cumulative_sum - targetSum) exists in our map. If yes, it means there are paths ending at current node with sum equal to targetSum.

The key optimization is that we don't need to recompute all path sums - instead we maintain a map of prefix sums and use the mathematical property that if sum[0..i] - sum[0..j] = target, then sum[j+1..i] = target.

Final approach with step-by-step reasoning:

1. Use DFS traversal to process nodes in pre-order
2. Maintain a HashMap storing prefix sums and their frequencies
3. At each node, compute current cumulative sum from root
4. Check if (current_sum - targetSum) exists in map - if yes, add count to result
5. Update the map with current sum's frequency
6. Recursively process children
7. Backtrack by decrementing frequency before returning to parent

Important invariants that must hold:

• The map always contains prefix sums from root to current node's ancestors
• For any valid path, we can find it by checking if (current_sum - target) exists in map
• We must handle the case where current_sum equals target (which means path from root to current node is valid)
• Map must be properly maintained during backtracking to avoid overcounting

Why this approach works: This approach leverages the mathematical property that if we have prefix sums, any subarray sum can be computed as difference between two prefix sums. In tree context, this means we can find all paths ending at current node that sum to target by looking for previous prefix sums that satisfy the equation.

4. Data Structure Choice

For tree path sum problems, the primary data structures are:

1. TreeNode class with value, left, and right pointers

• Essential for representing the tree structure
• Required to traverse and process nodes
• Space complexity: O(n) where n is the number of nodes

2. Stack for iterative DFS traversal

• Used to simulate recursion and avoid stack overflow for deep trees
• Enables us to track the current path from root to current node
• Space complexity: O(h) where h is the height of the tree (O(log n) for balanced, O(n) for skewed)
• More efficient than recursive stack for very deep trees

3. List/ArrayList to maintain current path

• Stores the path from root to current node for sum calculation
• Enables backtracking when exploring different branches
• Space complexity: O(h) for path storage

4. Integer variable to track current sum

• Keeps running total of values along the current path
• Space complexity: O(1) - constant space

5. Set/HashSet for storing unique sums (if needed)

• When problem requires counting distinct path sums
• Space complexity: O(k) where k is the number of unique sums

The key insight is that we need to maintain path information during traversal but don't want to store all paths explicitly. Instead, we track the current path sum and use it for comparison with target values.

The stack-based approach is preferred over pure recursion because:

• It avoids potential stack overflow on very deep trees
• It gives us explicit control over the traversal state
• It allows for easier modification if we need to return actual paths rather than just counts

For the specific case of counting paths with target sum, we don't need to store all previous sums in a separate data structure - we can calculate the difference on-the-fly using prefix sums and a HashMap for efficient lookup.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

Example: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

Step 1: Start at root node with value 5. Current path sum = 5, remaining target = 17.

Step 2: Explore left subtree (value 4). Path sum becomes 9, remaining target = 13.

Step 3: Continue down left path to node with value 11. Path sum = 20, remaining target = 2.

Step 4: At leaf node with value 7. Path sum = 27, which exceeds target. Backtrack.

Step 5: Back to node with value 11, try right child (value 2). Path sum = 22, remaining target = 0.

Step 6: Found valid path [5,4,11,2] with sum = 22. Add to result list.

Step 7: Continue backtracking, explore right subtree of root (value 8).

Step 8: At node with value 13. Path sum = 23, remaining target = -1.

Step 9: At node with value 4. Path sum = 17, remaining target = 5.

Step 10: At leaf node with value 5. Path sum = 22, remaining target = 0.

Step 11: Found second valid path [5,8,4,5] with sum = 22.

Step 12: Continue exploring remaining paths until all are exhausted.

The algorithm maintains the invariant that at each recursive call, we're tracking the current path sum and remaining target. When we reach a leaf node, we check if the remaining target is zero to confirm path validity.

The key insight is that we can't simply track a single running sum because we need to know which nodes are part of the current path to return the actual paths, not just whether they exist.

graph TD
    A[5] --> B[4]
    A --> C[8]
    B --> D[11]
    D --> E[7]
    D --> F[2]
    C --> G[13]
    C --> H[4]
    H --> I[5]
    H --> J[1]

6. Java Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // Main method to check if there exists a root-to-leaf path with given sum
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // Handle null tree case
        if (root == null) {
            return false;
        }
        
        // If we reached a leaf node, check if remaining sum equals node value
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }
        
        // Recursively check left and right subtrees with updated target sum
        return hasPathSum(root.left, targetSum - root.val) || 
               hasPathSum(root.right, targetSum - root.val);
    }
    
    // Alternative: Find all paths that sum to target (returns list of paths)
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, targetSum, new ArrayList<>(), result);
        return result;
    }
    
    private void dfs(TreeNode node, int remainingSum, List<Integer> currentPath, 
                     List<List<Integer>> result) {
        if (node == null) {
            return;
        }
        
        // Add current node to path
        currentPath.add(node.val);
        
        // Check if we reached a leaf and sum matches
        if (node.left == null && node.right == null && remainingSum == node.val) {
            result.add(new ArrayList<>(currentPath));
        } else {
            // Continue DFS on children
            dfs(node.left, remainingSum - node.val, currentPath, result);
            dfs(node.right, remainingSum - node.val, currentPath, result);
        }
        
        // Backtrack: remove current node from path
        currentPath.remove(currentPath.size() - 1);
    }
}

The solution implements two approaches:

1. hasPathSum - Returns boolean indicating if any root-to-leaf path sums to target
2. pathSum - Returns all root-to-leaf paths that sum to target

Both use DFS with backtracking. The first uses simple recursion, while the second maintains a path list that gets cloned when valid paths are found. The key insight is that we can either track sum as we go or check at leaf nodes, with the latter being more intuitive for path reconstruction.

7. Complexity Analysis

Time Complexity: O(N) where N is the number of nodes in the binary tree.

The algorithm performs a single traversal of the tree using DFS, visiting each node exactly once. At each node, we perform O(1) work: checking if the current path sum equals the target, updating the path sum, and maintaining the hash map operations (put/get/remove). Since each node is processed once and all operations at each node are constant time, the overall time complexity is linear in the number of nodes.

Space Complexity: O(H) where H is the height of the binary tree.

The space complexity comes from two sources:

1. The recursion stack depth, which is at most O(H) in the worst case (for a skewed tree) or O(log N) for a balanced tree
2. The HashMap storing prefix sums, which can contain at most O(H) entries in the worst case (when we have a path from root to leaf with all unique prefix sums)

In the worst case of a skewed tree, both the recursion stack and hash map can grow to O(N) in space, but for a balanced tree, the space usage is O(log N). The hash map's size is bounded by the maximum depth of the tree since we only store prefix sums for the current path from root to current node.

The solution is optimal because:

• We must visit each node at least once to determine if any path sums to the target
• The hash map operations are O(1) amortized, giving us linear time complexity
• We cannot avoid the space needed to track prefix sums for the path sum calculation

This is near-optimal for the problem as there's no way to avoid processing all nodes and maintaining path information to solve the path sum query efficiently.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty tree: Handle null root gracefully to avoid null pointer exceptions
• Single node: Verify that a tree with only root node works correctly (both positive and negative values)
• Single path: Ensure that a tree with one path from root to leaf works correctly

Duplicate Values and Repeated States

• Negative values: The algorithm must handle negative numbers correctly, as they can affect path sums
• Zero values: Zeroes in the tree can create multiple valid paths with same sum, requiring careful handling
• Duplicate sums: When multiple paths have the same sum, ensure all are counted correctly

Boundary Conditions

• All negative numbers: The algorithm should return the maximum single node value, not a sum of multiple nodes
• Large integer values: Handle potential overflow in sum calculations (though not an issue with int in most cases)
• Deep trees: Ensure stack overflow isn't an issue for very deep trees (though recursion depth is acceptable in most cases)

Common Implementation Mistakes

• Incorrect path termination: For "path from root to any node", ensure we don't accidentally consider paths that don't start at root
• Misunderstanding the path definition: Confusing "path from root to any node" vs "any path in tree"
• Not maintaining proper state: For recursive approaches, ensure that we don't accidentally reuse or share state between recursive calls
• Incorrect return value: Returning 0 instead of the actual maximum sum when all values are negative
• Missing edge case handling: For example, not handling the case where root == null properly

Specific Path Sum Issues

• Path must be downward: Ensure that paths can only go from parent to child (not up to parent or sideways)
• Root-to-leaf vs root-to-any-node: Different problems require different path definitions, and mixing them up is a common mistake
• Sum overflow: Though less likely in typical test cases, integer overflow can occur with very large numbers

Implementation-specific Pitfalls

• Global variables in recursive solutions: Avoid using global variables for tracking maximums, as they can cause issues with test isolation
• Incorrect base cases: For example, returning 0 instead of Integer.MIN_VALUE for maximum path sum when all nodes are negative
• Missing proper initialization: Not initializing the global max variable correctly before traversal

9. Alternative Approaches

There are several alternative approaches to solving tree path sum problems, each with different trade-offs:

1. Iterative DFS with Stack Instead of recursion, we can use an explicit stack to simulate the DFS traversal. This approach avoids potential stack overflow issues with very deep trees and gives us more control over the traversal state. The time complexity remains O(n) but we use O(h) space for the stack where h is the height of the tree.

2. BFS with Queue We could solve this using breadth-first search, maintaining a queue of nodes along with their cumulative sums. This approach is less intuitive for path problems but works by tracking all possible paths from root to each node. Time complexity is still O(n) but space usage can be higher as we might store multiple path sums.

3. Two-Pass Approach with Path Tracking We could make two passes through the tree: first to compute all path sums from root to each node, then to find valid combinations. This approach would require storing intermediate path information and is less efficient than our single-pass solution.

4. Bottom-Up Dynamic Programming For some variants, we might consider a bottom-up approach where we compute path sums from leaves upward. However, this is typically more complex and less intuitive than our top-down approach.

The chosen solution is preferred because it's clean, efficient, and handles the path tracking naturally with a single pass through the tree. The iterative approaches are more complex to implement correctly and don't provide significant advantages for this specific problem type.

10. Test Cases

public class TestCaseGenerator {
    // Test case 1: Basic valid case
    // Input: [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
    // Expected: true (5->4->11->2 = 22)
    public void testBasicValidPath() {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.right.right = new TreeNode(1);
        
        Solution solution = new Solution();
        boolean result = solution.hasPathSum(root, 22);
        assert result == true : "Test case 1 failed";
    }
    
    // Test case 2: Empty tree
    // Input: null, targetSum = 0
    // Expected: false
    public void testEmptyTree() {
        Solution solution = new Solution();
        boolean result = solution.hasPathSum(null, 0);
        assert result == false : "Test case 2 failed";
    }
    
    // Test case 3: Single node with matching sum
    // Input: [1], targetSum = 1
    // Expected: true
    public void testSingleNodeMatch() {
        TreeNode root = new TreeNode(1);
        Solution solution = new Solution();
        boolean result = solution.hasPathSum(root, 1);
        assert result == true : "Test case 3 failed";
    }
    
    // Test case 4: Single node with mismatched sum
    // Input: [1], targetSum = 2
    // Expected: false
    public void testSingleNodeMismatch() {
        TreeNode root = new TreeNode(1);
        Solution solution = new Solution();
        boolean result = solution.hasPathSum(root, 2);
        assert result == false : "Test case 4 failed";
    }
    
    // Test case 5: Path exists but not from root to leaf
    // Input: [1,2], targetSum = 3
    // Expected: true (1->2 = 3)
    public void testPathFromRootToLeaf() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        Solution solution = new Solution();
        boolean result = solution.hasPathSum(root, 3);
        assert result == true : "Test case 5 failed";
    }
    
    // Test case 6: Negative numbers in tree
    // Input: [1,-2,-3,1,3,-2,null,-1], targetSum = -1
    // Expected: true (1->-2->3 = 2, but 1->-2->1->-1 = 0, and 1->-3->-2 = -4)
    public void testNegativeNumbers() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(-2);
        root.right = new TreeNode(-3);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(-2);
        root.left.left.left = new TreeNode(-1);
        
        Solution solution = new Solution();
        boolean result = solution.hasPathSum(root, -1);
        assert result == true : "Test case 6 failed";
    }
    
    // Test case 7: All zeros in tree
    // Input: [0,0,0], targetSum = 0
    // Expected: true (0->0 = 0, 0->0 = 0)
    public void testAllZeros() {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(0);
        root.right = new TreeNode(0);
        
        Solution solution = new Solution();
        boolean result = solution.hasPathSum(root, 0);
        assert result == true : "Test case 7 failed";
    }
}

11. Final Summary

The core idea is to use depth-first search with backtracking to explore all possible root-to-leaf paths while maintaining a running sum, efficiently pruning branches that exceed the target sum. This solution works by leveraging the call stack to naturally manage path tracking and backtracking, making it both intuitive and memory-efficient. The approach is optimal with O(n) time complexity for a binary tree of n nodes, as each node is visited exactly once, and O(h) space complexity where h is the tree height due to recursion stack depth.