Path Sum II

109.Path Sum II

Tree

Depth-First Search

Backtracking

Problem Statement:

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path's sum equals targetSum. A leaf is a node with no children.

Algorithm:

1. Perform a depth-first search (DFS) on the tree to explore all root-to-leaf paths.
2. Maintain a temporary list to store the current path.
3. For each node:
   • Add the node's value to the path.
   • If the node is a leaf and the remaining sum equals the node's value, add the path to the result list.
   • Recurse into the left and right subtrees, reducing the sum by the node's value.
   • Backtrack by removing the node's value from the path after exploring its children.
4. Return the list of all valid paths.

Complexity:

Time: O(n), where n is the number of nodes in the tree | Space: O(h), where h is the height of the tree (for recursion stack).

Java Implementation:

import java.util.*;

public class Solution {
    public List> pathSum(TreeNode root, int sum) {
        List> result = new ArrayList<>();
        List tempList = new ArrayList<>();
        dfs(root, result, tempList, sum);
        return result;
    }

    public void dfs(TreeNode node, List> result, List tempList, int sum) {
        if (node == null) return;

        tempList.add(node.val);

        // Check if it's a leaf and the sum matches
        if (node.left == null && node.right == null && sum - node.val == 0)
            result.add(new ArrayList<>(tempList));

        // Recurse into left and right subtrees
        dfs(node.left, result, tempList, sum - node.val);
        dfs(node.right, result, tempList, sum - node.val);

        // Backtrack
        tempList.remove(tempList.size() - 1);
    }
}
                

Python Implementation:

def pathSum(root, targetSum):
    result = []

    def dfs(node, path, remaining_sum):
        if not node:
            return
        
        path.append(node.val)

        # Check if it's a leaf and the sum matches
        if not node.left and not node.right and remaining_sum == node.val:
            result.append(list(path))

        # Recurse into left and right subtrees
        dfs(node.left, path, remaining_sum - node.val)
        dfs(node.right, path, remaining_sum - node.val)

        # Backtrack
        path.pop()

    dfs(root, [], targetSum)
    return result
                

C++ Implementation:

#include 
using namespace std;

class Solution {
public:
    vector> pathSum(TreeNode* root, int targetSum) {
        vector> result;
        vector path;
        dfs(root, targetSum, path, result);
        return result;
    }

    void dfs(TreeNode* node, int remainingSum, vector& path, vector>& result) {
        if (!node) return;

        path.push_back(node->val);

        // Check if it's a leaf and the sum matches
        if (!node->left && !node->right && remainingSum == node->val) {
            result.push_back(path);
        }

        // Recurse into left and right subtrees
        dfs(node->left, remainingSum - node->val, path, result);
        dfs(node->right, remainingSum - node->val, path, result);

        // Backtrack
        path.pop_back();
    }
};