113. Path Sum II

Problem Statement

Given a binary tree and a target sum, find all root-to-leaf paths where the sum of the node values in the path equals the target sum. Each path should be represented as a list of integers from the root to the leaf.

Example:

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

codeInput: root = [1,2,3], targetSum = 5
Output: []

codeInput: root = [1,2], targetSum = 1
Output: []

Approach

To solve this problem, we use a depth-first search (DFS) approach:

Recursive DFS Traversal: Traverse the binary tree starting from the root. For each node, subtract its value from the target sum and continue the search in its left and right subtrees.
Path Tracking: Maintain a list to track the current path. Add the node’s value to this list as we traverse down and remove it when backtracking.
Check Path Validity: When a leaf node is reached, check if the remaining target sum is zero. If so, add the current path to the result list.

Solution

Here’s the Java code implementing the above approach:

javaCopy codeimport java.util.*;

/**
 * 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>> res = new ArrayList<>();
        helper(root, targetSum, new ArrayList<Integer>(), res);
        return res;
    }

    void helper(TreeNode root, int targetSum, ArrayList<Integer> sol, List<List<Integer>> res) {
        if (root == null) return;

        // Add the current node’s value to the path
        sol.add(root.val);

        // Check if it’s a leaf node and the path’s sum equals the target
        if (root.left == null && root.right == null && targetSum == root.val) {
            res.add(new ArrayList<>(sol));
        } else {
            // Continue the search on the left and right subtrees
            helper(root.left, targetSum - root.val, sol, res);
            helper(root.right, targetSum - root.val, sol, res);
        }

        // Backtrack: remove the last node’s value before returning
        sol.remove(sol.size() - 1);
    }
}

Analysis

Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited once.
Space Complexity: O(H⋅L), where H is the height of the tree and L is the maximum length of a path. This includes space for the recursion stack and the list of results.

Conclusion

This solution effectively identifies all root-to-leaf paths that sum up to a given target using a depth-first search strategy. By maintaining a running list of node values and verifying against the target sum, the algorithm efficiently finds and returns all valid paths. This approach ensures comprehensive tree traversal with manageable space complexity.

You can find all my solutions at Github

Thank you for reading! Stay tuned for the next article in this series, where we'll tackle another exciting LeetCode problem.

113. Path Sum II

Comments

LeetCode

3. Longest Substring Without Repeating Characters

More from this blog

Designing Web APIs: Chapter 7 - Managing Change

Designing Web APIs: Chapter 6 - Scaling APIs

Designing Web APIs: Chapter 5 - Design In Practice

Designing Web APIs: Chapter 4 - Design Best Practices

Designing Web APIs: Chapter 3 - API Security

Problem Statement

Approach

Solution

Analysis

Conclusion

Command Palette

Comments

LeetCode

3. Longest Substring Without Repeating Characters

More from this blog

Problem Statement

Approach

Solution

Analysis

Conclusion