113. Path Sum II

Tree Depth-First Search Backtracking Binary Tree

Time: O(n²)

Space: O(n)

Intuition

Same as Path Sum I but record the current path when a valid leaf is found. Use backtracking to maintain the path: add node before recursion, remove after.

Algorithm

1DFS(node, remaining, path, result):
2If null, return.
3Add node.val to path. remaining -= node.val.
4If leaf and remaining == 0: add copy of path to result.
5Else: recurse left and right.
6Remove last element from path (backtrack).

Example Walkthrough

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

1.Path 5->4->11->2: sum=22 . Record [5,4,11,2]. Backtrack.
2.Path 5->8->4->5: sum=22 . Record [5,8,4,5].

Output: [[5,4,11,2],[5,8,4,5]]

Common Pitfalls

•Add a COPY of path (new List), not a reference - otherwise all recorded paths will be mutated by subsequent backtracking.

113.cs

// Approach: DFS with backtracking — append the node at entry and remove it
// on exit; record the path when a leaf is reached with remaining sum zero.
// Time: O(n²) Space: O(n)

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    public IList<IList<int>> PathSum(TreeNode root, int targetSum)
    {
        IList<IList<int>> result = new List<IList<int>>();
        List<int> ds = new();
        PSIIDFS(root, targetSum, ds, result);
        return result;
    }

    private void PSIIDFS(TreeNode root, int targetSum, IList<int> ds, IList<IList<int>> result)
    {
        if (root == null)
            return;

        if (root.val == targetSum && root.left == null && root.right == null)
        {
            ds.Add(root.val);
            result.Add(new List<int>(ds));
            ds.RemoveAt(ds.Count - 1);
            return;
        }

        ds.Add(root.val);
        PSIIDFS(root.left, targetSum - root.val, ds, result);
        PSIIDFS(root.right, targetSum - root.val, ds, result);
        ds.RemoveAt(ds.Count - 1);
    }
}

Was this solution helpful?