Path Sum II Java Solution with DFS and Backtracking

Path Sum II requires finding all root-to-leaf paths in a binary tree where the sum of node values equals a target value. This solution uses depth-first search with backtracking to efficiently explore all possible paths while maintaining optimal space complexity.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input tree be mutated during processing, or must we preserve the original structure?
2. What is the expected return format for path sums - should we return all valid paths or just a boolean?
3. Are there any constraints on the number of nodes in the tree (e.g., max 10^4 nodes)?
4. Should we handle negative node values, or can we assume all values are positive?
5. What is the target time complexity - O(n) or O(n log n) acceptable?

Restatement in my own words: Given a binary tree where each node contains an integer value, we need to find all root-to-leaf paths that sum up to a given target value. Each path should contain the actual node values in sequence, not just their sum.

Input/output specification:

• Input: Root of a binary tree and an integer target sum
• Output: List of lists, where each inner list represents a valid root-to-leaf path that sums to the target

Constraints:

• Binary tree can have up to 10^4 nodes (assuming typical FAANG constraints)
• Node values can be negative, zero, or positive integers
• Tree structure is not necessarily balanced

Assumptions:

• The tree is a standard binary tree with left and right children
• We're looking for root-to-leaf paths (not just any path)
• The target sum can be achieved through a combination of positive and negative values
• We don't need to mutate the input tree structure

Data shape and hidden structure: The problem involves traversing a binary tree with backtracking to maintain path information. The key insight is that we need to track the current path from root to current node and backtrack when exploring different branches. The structure is hierarchical with parent-child relationships that form paths, making this a classic tree traversal + backtracking problem.

The problem has a hidden structure where we're essentially maintaining a "path state" that gets updated during DFS traversal and backtracked when moving between sibling branches.

2. Pattern Recognition

Identifying the pattern

This problem exhibits the Tree Path Traversal pattern, specifically Backtracking with Path Tracking. The key indicators are:

• We're dealing with a binary tree structure
• We need to find paths from root to leaf that meet a specific condition (sum equals target)
• Each path must maintain state as we traverse down the tree
• We're collecting multiple valid solutions rather than just one

Wording that signals the pattern

The problem statement mentions "root-to-leaf paths" and "sum of all node values along the path". These phrases indicate we're looking at a tree traversal where:

• We must go from root to leaf (not just any path)
• We're accumulating values along the way
• We need to collect all valid paths that meet a condition

Why this fits the pattern

This is fundamentally about path enumeration with constraints. The tree structure naturally suggests a recursive approach, and the requirement to collect all valid paths rather than just checking existence makes this a classic backtracking problem. Each decision point (node choice) affects the path sum, and we must explore all valid combinations.

Core insight

The key insight is that we can use recursive DFS with path tracking to explore all root-to-leaf paths. At each node, we:

1. Add the current node's value to our running path sum
2. If we're at a leaf and sum matches target, record the path
3. Recursively explore left and right subtrees
4. Backtrack by removing current node from path (this is the "backtracking" part)

This approach naturally handles the constraint that paths must be from root to leaf, and we can efficiently collect all valid solutions by maintaining the current path state throughout the traversal.

3. Approach Evolution

My first instinct is to use a depth-first search (DFS) approach because this is fundamentally a tree traversal problem where we need to explore all possible paths from root to leaves. However, that would be O(n²) in the worst case if we're checking all paths from every node, which is inefficient.

Let me think about how to optimize this. I notice that if I maintain a running sum from root to current node, and I can track the path taken so far, I can reduce it to O(n) time complexity by visiting each node only once.

The key insight is that for any path from root to leaf, I need to:

1. Keep track of the current sum along the path
2. Store the actual path elements to return when I reach a leaf
3. When I reach a leaf, check if the sum equals targetSum

I'm thinking of a recursive DFS approach where:

• I pass the current node, current sum, and current path to each recursive call
• When I hit a leaf node, I check if the sum matches targetSum
• If it does, I add the current path to my result list

This approach maintains the invariant that at any point in the traversal, I have the complete path from root to current node, and I'm only storing valid paths that sum to targetSum when they reach a leaf.

The optimization comes from avoiding redundant computations - I don't need to recompute sums or paths, I just maintain the running state and only store results when I reach a leaf with matching sum.

This is more efficient than the brute force approach because:

1. Each node is visited exactly once (O(n) time)
2. Path storage is only done for valid solutions (not all paths)
3. I don't need to backtrack or recompute anything

The approach is clean, intuitive, and optimal for this specific problem structure.

4. Data Structure Choice

For this path sum problem, I'll use a combination of data structures:

Primary Data Structures:

1. TreeNode class - This is the core input structure representing the binary tree nodes. Each node contains a value and references to left and right children.

2. List<List<Integer>> - Used to store all valid paths from root to leaf that sum to the target. This is the required output format where each inner list represents one valid path.

3. List<Integer> - Used as a temporary working list to build the current path during DFS traversal. This gets cloned and added to the result when we reach a valid leaf node.

Why Each Data Structure Is Needed:

The TreeNode class is essential as it defines the input structure and provides the tree traversal capabilities. The List<List<Integer>> is required to collect all valid paths as specified in the problem requirements.

The List<Integer> serves as a dynamic working set that accumulates node values during the depth-first search. It's crucial to understand that we must clone this list when adding it to our result to avoid reference issues - otherwise, all entries in the final result would point to the same mutable list object.

Time and Space Impact:

• The TreeNode structure is O(1) space per node, so O(n) total for n nodes
• The List<Integer> maintains at most O(h) elements where h is the tree height (O(log n) for balanced trees, O(n) for skewed trees)
• The result List<List<Integer>> can contain up to O(2^h) paths in worst case (for a complete binary tree), each with up to O(h) elements
• Space complexity is dominated by the result storage: O(2^h × h) = O(n × log n) in worst case

Helper Structures:

• Stack-like behavior via recursion - While not explicitly declared, the call stack serves as a natural way to maintain path state during DFS traversal
• Clone operation - We use new ArrayList<>(currentPath) to create independent copies of the path for storage

This choice enables clean, readable code while maintaining optimal performance characteristics for the recursive DFS approach. The combination of these structures allows us to efficiently build and track paths while avoiding expensive deep copies until the final storage step.

5. Algorithm Walkthrough

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

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

Step 1: Start with root node (5), current path = [5], remaining sum = 22 - 5 = 17

Step 2: Go to left child (4), current path = [5,4], remaining sum = 17 - 4 = 13

Step 3: Go to left child (11), current path = [5,4,11], remaining sum = 13 - 11 = 2

Step 4: Go to left child (7), current path = [5,4,11,7], remaining sum = 2 - 7 = -5

• This is negative, so we backtrack and remove 7 from path

Step 5: Go to right child (2), current path = [5,4,11,2], remaining sum = 2 - 2 = 0

• Remaining sum is 0, so we found a valid path [5,4,11,2]
• Add this to result list: [[5,4,11,2]]

Step 6: Backtrack to node (11), then to node (4), then to node (5)

Step 7: Go to right child of root (8), current path = [5,8], remaining sum = 17 - 8 = 9

Step 8: Go to left child (13), current path = [5,8,13], remaining sum = 9 - 13 = -4

• This is negative, so we backtrack and remove 13 from path

Step 9: Go to right child (4), current path = [5,8,4], remaining sum = 9 - 4 = 5

Step 10: Go to left child (5), current path = [5,8,4,5], remaining sum = 5 - 5 = 0

• Remaining sum is 0, so we found a valid path [5,8,4,5]
• Add this to result list: [[5,4,11,2], [5,8,4,5]]

Step 11: Go to right child (1), current path = [5,8,4,1], remaining sum = 5 - 1 = 4

• This is positive but we're at a leaf node, so continue backtracking

Step 12: Backtrack completely and return result list

The key insight is that we explore all possible paths using DFS with backtracking. At each leaf node, we check if the remaining sum equals zero to validate that path. The algorithm maintains the invariant that the current path always represents a valid path from root to current node, and we properly backtrack by removing nodes when we explore alternative branches.

// Example trace:
// Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
// Path [5] -> [5,4] -> [5,4,11] -> [5,4,11,7] (sum = -5) -> backtrack
// Path [5,4,11,2] (sum = 0) -> valid path found
// Path [5,8] -> [5,8,13] (sum = -4) -> backtrack
// Path [5,8,4] -> [5,8,4,5] (sum = 0) -> valid path found
// Result: [[5,4,11,2], [5,8,4,5]]

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 {
    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) {
        // Base case: if node is null, return
        if (node == null) {
            return;
        }
        
        // Add current node value to path
        currentPath.add(node.val);
        
        // Check if it's a leaf node and remaining sum equals node value
        if (node.left == null && node.right == null && remainingSum == node.val) {
            // Found a valid path, add it to result
            result.add(new ArrayList<>(currentPath));
        } else {
            // Continue DFS on left and right subtrees
            dfs(node.left, remainingSum - node.val, currentPath, result);
            dfs(node.right, remainingSum - node.val, currentPath, result);
        }
        
        // Backtrack: remove current node from path before returning
        currentPath.remove(currentPath.size() - 1);
    }
}

The solution uses a depth-first search approach with backtracking to find all root-to-leaf paths that sum to the target value. For each node, we maintain the current path and remaining sum, recursively exploring left and right subtrees while properly managing the path state through backtracking.

7. Complexity Analysis

Time Complexity: O(N × M) where N is the number of nodes in the binary tree and M is the average path length from root to leaf.

In the worst case, we visit each node exactly once and for each node, we may need to copy the current path (which can be up to O(H) where H is the height of the tree). Since we're storing all valid paths, and there could be up to O(2^H) leaf paths in a complete binary tree, the total time complexity becomes O(N × M), where M represents the average path length.

Space Complexity: O(H × 2^H)

The space complexity has two components:

1. Recursive call stack: O(H) where H is the height of the tree (in worst case for skewed trees, this becomes O(N))
2. Storage for paths: In the worst case (complete binary tree), there are O(2^H) leaf nodes, and each path can be up to O(H) long. So we need O(2^H × H) space for storing all paths.

In the average case (balanced tree), this becomes O(log N × 2^(log N)) = O(N log N) where H ≈ log N.

The solution is optimal for this problem since we must examine every node at least once to determine valid paths, and we must store all valid paths in the output. The solution achieves linear time complexity with respect to the number of nodes and optimal space usage for storing all paths.

The complexity analysis assumes that path copying is proportional to the path length, which is a reasonable assumption for this problem's constraints.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty tree: When root == null, the solution should return an empty list of paths. This is a critical base case that must be handled early.
• Single node tree: When root is not null but both left and right children are null, the solution should return a list containing one path with just that node's value.

Duplicate Values and Repeated States

• Negative values: The algorithm must handle negative node values correctly, as they can make or break a valid path sum.
• Duplicate sums: Multiple paths can have the same sum, and all such paths must be included in the result.
• Zero values: Zero-valued nodes can create multiple valid paths and must not be ignored.

Boundary Conditions

• Target sum = 0: The algorithm should correctly handle cases where the target sum is zero, which can occur with negative numbers or zero-valued nodes.
• Very large sums: When dealing with large integer values, overflow considerations should be noted (though not explicitly required for this problem).
• Tree with only negative values: All paths will have negative sums, so the solution must correctly filter based on the target sum.

Common Implementation Mistakes

• Modifying input tree: A common mistake is modifying the original tree structure during traversal, which violates the constraint that the input should remain unchanged.
• Incorrect path tracking: Not properly maintaining the current path during backtracking can lead to incorrect results. Each recursive call should work with its own copy of the path.
• Missing base case handling: Failing to properly handle null nodes or leaf nodes can cause NullPointerExceptions or incorrect path inclusion.
• Not using proper backtracking: When adding a node to the current path, it must be removed after exploring all branches from that node (backtracking).
• Incorrect termination condition: Using currentSum == targetSum as the only exit condition without proper path validation can lead to incorrect results.

The solution must be robust enough to handle all these edge cases while maintaining correctness and efficiency.

9. Alternative Approaches

There are several alternative approaches to solving the Path Sum problem, 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. Each stack element would need to track both the current node and the accumulated path sum so far.

2. BFS with Queue We could use breadth-first search instead of depth-first search, maintaining a queue of (node, current_sum) pairs. This approach would naturally find all paths to leaf nodes but requires more memory to store the queue state and is less intuitive for path problems.

3. Two-Pass Approach (Preprocessing) First, we could precompute all possible path sums from root to each node and store them in a hash map. Then, for each leaf node, we could check if the difference between targetSum and that node's accumulated sum equals zero. However, this approach is overly complex for the problem and doesn't leverage the tree structure effectively.

4. Backtracking with Path Tracking Instead of passing a running sum, we could maintain the actual path from root to current node and compute the sum when reaching a leaf. This is more memory-intensive but provides direct access to the path elements for further processing.

The chosen recursive approach with early termination is optimal because it's clean, readable, and efficiently prunes invalid branches. The iterative alternatives add complexity without significant benefit for this specific problem structure, while the two-pass approach introduces unnecessary overhead. The backtracking variant would work but requires more careful handling of path state management.

The chosen solution strikes the best balance between simplicity, efficiency, and clarity for this particular tree traversal problem.

10. Test Cases

// Test case 1: Basic valid path
// Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
// Expected: [[5,4,11,2],[5,8,4,5]]
// Path 1: 5->4->11->2 = 22
// Path 2: 5->8->4->5 = 22

// Test case 2: Empty tree
// Input: root = [], targetSum = 0
// Expected: []

// Test case 3: Single node with matching value
// Input: root = [1], targetSum = 1
// Expected: [[1]]

// Test case 4: Single node with mismatched value
// Input: root = [1], targetSum = 2
// Expected: []

// Test case 5: Multiple paths with same sum
// Input: root = [1,2,3,4,5], targetSum = 7
// Expected: [[1,2,4],[1,3,3]] - assuming 3 appears twice in tree structure

// Test case 6: Negative numbers
// Input: root = [1,-2,-3,1,3,-2,null,-1], targetSum = -1
// Expected: [[1,-2,1,-1],[1,-3,1]]

// Test case 7: Target sum of 0 with negative values
// Input: root = [0,1,2], targetSum = 0
// Expected: [[0]]

// Test case 8: Large tree with many valid paths
// Input: root = [1,2,3,4,5,6,7], targetSum = 10
// Expected: [[1,2,4,3],[1,3,6]]

// Test case 9: Path that includes leaf nodes only
// Input: root = [1,2,3,null,4,null,5], targetSum = 7
// Expected: [[1,2,4],[1,3,5]]

The test cases cover various scenarios including:

• Basic valid paths with multiple solutions
• Edge cases like empty trees and single nodes
• Negative numbers and zero sums
• Tree structures with multiple valid paths
• Boundary conditions with minimal inputs

Each test case verifies different aspects of the solution's correctness and handles various tree configurations that could challenge the implementation.

11. Final Summary

The core idea is to perform a depth-first search with backtracking to explore all possible root-to-leaf paths while maintaining the current path and running sum. This approach works efficiently by avoiding redundant computations through careful path management and early termination when paths exceed the target sum.

The solution is optimal because it visits each node exactly once with O(n) time complexity, and the space complexity of O(h) where h is the height represents the maximum recursion stack depth plus the path storage. The backtracking technique ensures we don't need to create new path copies at each node, making the space usage minimal and efficient for the problem's constraints.

What makes this solution particularly strong is its clean separation of concerns: path tracking, sum calculation, and termination conditions are all handled elegantly through the recursive structure, with proper cleanup after exploring each branch to prevent path contamination.