Java - Paths from root with a specified sum

Problem Statement

You're given a binary tree and a target sum.

Find all paths that start at the root node and add up to the target sum.

The path can end at any node, not just leaf nodes.

Approach

Use Depth-First Search (DFS).

Keep track of:

The current path.

The current sum.

If current sum == target, store the path.

Use backtracking to revert the path after exploring both subtrees.

Java Code

import java.util.*;

class TreeNode {

    int val;

    TreeNode left, right;

    TreeNode(int val) {

        this.val = val;

    }

}

class Solution {

    public List<List<Integer>> findPaths(TreeNode root, int target) {

        List<List<Integer>> result = new ArrayList<>();

        List<Integer> path = new ArrayList<>();

        dfs(root, 0, target, path, result);

        return result;

    }

    private void dfs(TreeNode node, int currSum, int target, List<Integer> path, List<List<Integer>> result) {

        if (node == null) return;

        currSum += node.val;

        path.add(node.val);

        if (currSum == target) {

            result.add(new ArrayList<>(path));

        }

        dfs(node.left, currSum, target, path, result);

        dfs(node.right, currSum, target, path, result);

        path.remove(path.size() - 1); // Backtrack

    }

}

public class Main {

    public static void main(String[] args) {

        // Example Tree:

        TreeNode root = new TreeNode(5);

        root.left = new TreeNode(4);

        root.right = new TreeNode(8);

        root.left.left = new TreeNode(11);

        root.left.left.left = new TreeNode(7);

        root.left.left.right = new TreeNode(2);

        root.right.left = new TreeNode(13);

        root.right.right = new TreeNode(4);

        root.right.right.right = new TreeNode(1);

        int targetSum = 20;

        Solution solution = new Solution();

        List<List<Integer>> paths = solution.findPaths(root, targetSum);

        System.out.println("Paths with sum " + targetSum + ":");

        for (List<Integer> path : paths) {

            System.out.println(path);

        }

    }

}

Sample Output

Paths with sum 20:

[5, 4, 11]

[5, 8, 4, 1]