Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def pathSum(self, root, targetSum):
        res = []
        def dfs(node, path, curr_sum):
            if not node:
                return
            path.append(node.val)
            curr_sum += node.val
            if not node.left and not node.right and curr_sum == targetSum:
                res.append(list(path))
            else:
                dfs(node.left, path, curr_sum)
                dfs(node.right, path, curr_sum)
            path.pop()
        dfs(root, [], 0)
        return res
      

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> res;
        vector<int> path;
        dfs(root, targetSum, 0, path, res);
        return res;
    }
    void dfs(TreeNode* node, int targetSum, int curr_sum, vector<int>& path, vector<vector<int>>& res) {
        if (!node) return;
        path.push_back(node->val);
        curr_sum += node->val;
        if (!node->left && !node->right && curr_sum == targetSum) {
            res.push_back(path);
        } else {
            dfs(node->left, targetSum, curr_sum, path, res);
            dfs(node->right, targetSum, curr_sum, path, res);
        }
        path.pop_back();
    }
};
      

/**
 * 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<>();
        List<Integer> path = new ArrayList<>();
        dfs(root, targetSum, 0, path, res);
        return res;
    }
    private void dfs(TreeNode node, int targetSum, int currSum, List<Integer> path, List<List<Integer>> res) {
        if (node == null) return;
        path.add(node.val);
        currSum += node.val;
        if (node.left == null && node.right == null && currSum == targetSum) {
            res.add(new ArrayList<>(path));
        } else {
            dfs(node.left, targetSum, currSum, path, res);
            dfs(node.right, targetSum, currSum, path, res);
        }
        path.remove(path.size() - 1);
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number[][]}
 */
var pathSum = function(root, targetSum) {
    const res = [];
    function dfs(node, path, currSum) {
        if (!node) return;
        path.push(node.val);
        currSum += node.val;
        if (!node.left && !node.right && currSum === targetSum) {
            res.push([...path]);
        } else {
            dfs(node.left, path, currSum);
            dfs(node.right, path, currSum);
        }
        path.pop();
    }
    dfs(root, [], 0);
    return res;
};
      

Problem Description

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be represented as a list of node values. A root-to-leaf path is a path starting at the root node and ending at any leaf node (a node with no children).

• You may return the paths in any order.
• Each node can only be used once per path (no reuse).
• If there are no valid paths, return an empty list.

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -1000 ≤ Node.val ≤ 1000
• -1000 ≤ targetSum ≤ 1000

Thought Process

To solve this problem, we need to find all paths from the root to any leaf such that the sum of the node values along the path equals targetSum.

The most straightforward approach would be to try every possible path from the root to each leaf, keeping track of the sum as we traverse. If the sum matches targetSum at a leaf, we record that path.

However, this brute-force approach can be optimized by:

• Using recursion (Depth-First Search) to explore each path.
• Keeping a current path and sum as we traverse, so we can backtrack efficiently.
• Recording a path only if it ends at a leaf and the sum is exactly targetSum.

Solution Approach

We'll use a recursive Depth-First Search (DFS) algorithm for this problem. Here's how we approach it step by step:

1. Start at the root: Begin the traversal from the root node, with an empty path and a sum of zero.
2. Recursive exploration: At each node, add its value to the current path and update the running sum.
3. Check for leaf node: If the node is a leaf (no left or right child), and the running sum equals targetSum, record a copy of the current path.
4. Continue traversal: If not at a leaf, recursively call the function on the left and right children (if they exist).
5. Backtracking: After exploring both children, remove the current node's value from the path before returning to the previous call. This ensures that the path is correct for other branches.
6. Return results: When all paths have been explored, return the list of valid paths.

This approach is efficient because:

• Each node is visited once per path.
• Backtracking ensures we don't retain unnecessary state between different paths.
• We only record paths that end at leaves and match targetSum.

Example Walkthrough

Example: Suppose the binary tree is:

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1
  

And targetSum = 22.

Let's trace the algorithm:

• Start at 5: path = [5], sum = 5
• Go left to 4: path = [5, 4], sum = 9
• Go left to 11: path = [5, 4, 11], sum = 20
• Go left to 7: path = [5, 4, 11, 7], sum = 27 (not a match, backtrack)
• Go right to 2: path = [5, 4, 11, 2], sum = 22 (leaf and match, record path)
• Backtrack to 5, go right to 8: path = [5, 8], sum = 13
• Go left to 13: path = [5, 8, 13], sum = 26 (leaf, not a match, backtrack)
• Go right to 4: path = [5, 8, 4], sum = 17
• Go left to 5: path = [5, 8, 4, 5], sum = 22 (leaf and match, record path)
• Go right to 1: path = [5, 8, 4, 1], sum = 18 (not a match, backtrack)

The final result is two paths:

• [5, 4, 11, 2]
• [5, 8, 4, 5]

Time and Space Complexity

Brute-force Approach:

• In the worst case, every root-to-leaf path is explored. For a balanced tree with N nodes, there could be up to O(2^H) paths, where H is the height of the tree.
• Each path can be at most O(H) long, so total time is O(N) since every node is visited once per path.
• Space is O(H) for the recursion stack and the current path, plus O(K*H) for storing K valid paths.

• Each node is visited once, so time complexity is O(N).
• Space complexity is O(H) for the recursion stack and path, where H is the height of the tree.
• Output space may be up to O(K*H) if there are K valid paths.

Summary

The Path Sum II problem is elegantly solved using recursive DFS and backtracking. By keeping track of the current path and sum, we efficiently explore all root-to-leaf paths. The solution is both intuitive and optimal, leveraging the tree structure and recursion to avoid unnecessary work. Key insights include using backtracking to manage path state and only recording paths that meet the exact criteria at leaf nodes.