#113

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Path Sum II

Find all root-to-leaf paths in a binary tree where the sum of node values equals a given target using DFS backtracking.

backtracking tree depth first search binary tree

Problem Statement

Given a binary tree root and an integer targetSum, identify all root-to-leaf paths where the sum of node values equals targetSum. Each path should be represented as a list of integers reflecting node values along that path.

A root-to-leaf path starts at the root and ends at a leaf, which has no children. Return all possible paths satisfying the sum condition, maintaining order from root to leaf. For example, root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22, yields [[5,4,11,2],[5,8,4,5]].

Examples

Example 1

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

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

There are two paths whose sum equals targetSum: 5 + 4 + 11 + 2 = 22 5 + 8 + 4 + 5 = 22

Example 2

Input: root = [1,2,3], targetSum = 5

Output: []

Example details omitted.

Example 3

Input: root = [1,2], targetSum = 0

Output: []

Example details omitted.

Constraints

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

Solution Approach

Depth-First Search with Path Tracking

Use DFS to traverse the binary tree, maintaining a current path list and running sum. When a leaf node is reached, check if the sum equals targetSum, and if so, append a copy of the path to the results.

Backtracking to Explore All Paths

After visiting a node, recursively explore its children. Once both children are processed, remove the node from the current path to backtrack and explore alternative paths, ensuring no leftover state affects other paths.

Handle Edge Cases and Empty Trees

Ensure the function handles null roots, single-node trees, and paths where no combination meets the target. Early return for empty trees prevents unnecessary recursion and preserves correct path collection.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(N^2) in the worst case for a skewed tree because copying the path takes O(N) per leaf, with N nodes. Space complexity is O(N) for recursion stack and path storage.

What Interviewers Usually Probe

Asks about recursive vs iterative DFS approaches for path tracking.
Questions about handling negative values in node sums or targetSum.
Wants explanation on why backtracking is essential to avoid incorrect path accumulation.

Common Pitfalls or Variants

Common pitfalls

Forgetting to backtrack and remove the last node, corrupting future paths.
Returning paths before reaching leaf nodes, which violates root-to-leaf definition.
Not handling empty trees or single-node cases properly, leading to runtime errors.

Follow-up variants

Return only the first valid path instead of all paths.
Modify the problem to find paths summing to a target in a n-ary tree instead of binary tree.
Count the number of paths instead of returning the path lists.

FAQ

What is the main strategy for solving Path Sum II?

Use depth-first search combined with backtracking to track all root-to-leaf paths and validate their sums against targetSum.

How does backtracking help in this problem?

Backtracking ensures that after exploring a path, the last node is removed so alternative paths can be explored without carrying over previous state.

Can Path Sum II be solved iteratively?

Yes, using a stack to simulate DFS while storing current paths and running sums, but recursive DFS with backtracking is often simpler.

What are common mistakes when implementing Path Sum II?

Common mistakes include not removing nodes after recursion, checking sums before reaching leaves, or mishandling null trees.

Does negative values in nodes affect the approach?

No, DFS and backtracking handle negative values naturally as sums are evaluated at leaf nodes without assumptions about positivity.

terminal

Solution

Solution 1: DFS

We start from the root node, recursively traverse all paths from the root node to the leaf nodes, and record the path sum. When we traverse to a leaf node, if the current path sum equals `targetSum`, then we add this path to the answer.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

# 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: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        def dfs(root, s):
            if root is None:
                return
            s += root.val
            t.append(root.val)
            if root.left is None and root.right is None and s == targetSum:
                ans.append(t[:])
            dfs(root.left, s)
            dfs(root.right, s)
            t.pop()

        ans = []
        t = []
        dfs(root, 0)
        return ans

Continue Practicing

#257 binary tree paths #988 smallest string starting from leaf #112 path sum