LeetCode 113 - Path Sum II

This problem asks us to find all root-to-leaf paths in a binary tree where the sum of the node values equals a given targetSum. A binary tree is provided through the root node, and every node contains an integer value. We are also given an integer targetSum.

leetcodemediumbacktrackingtreedepth-first-searchbinary-tree

LeetCode Problem 113

Difficulty: 🟡 Medium
Topics: Backtracking, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to find all root-to-leaf paths in a binary tree where the sum of the node values equals a given targetSum.

A binary tree is provided through the root node, and every node contains an integer value. We are also given an integer targetSum. Our task is to explore every valid path that starts at the root and ends at a leaf node, then return only the paths whose total sum equals targetSum.

The important detail is that we are not looking for any arbitrary sequence of nodes. The path must satisfy two strict conditions:

  1. It must begin at the root.
  2. It must end at a leaf node, meaning a node with no left or right child.

The output should contain the values of nodes in each valid path, not references to the nodes themselves. Since multiple valid paths may exist, we return a list of lists.

For example, in the first example:

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

With targetSum = 22, there are two valid root-to-leaf paths:

5 → 4 → 11 → 2 = 22
5 → 8 → 4 → 5 = 22

So the answer becomes:

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

The constraints tell us that the tree may contain up to 5000 nodes, which is large enough that inefficient repeated traversal could become expensive. Node values and target sums can also be negative, meaning we cannot rely on pruning strategies such as stopping early when a sum exceeds the target. Since negative values are allowed, a larger sum can later decrease, and vice versa.

Several edge cases are important to consider upfront. The tree may be empty (root = None), in which case there are no paths. A tree may contain only one node, meaning the root is also a leaf. Negative values can create paths where sums fluctuate unexpectedly. Finally, multiple valid paths may exist, and we must ensure they are stored independently instead of accidentally modifying previously saved paths.

Approaches

Brute Force Approach

A straightforward brute-force solution is to first generate every root-to-leaf path in the tree and then calculate the sum of each path afterward.

To do this, we would recursively traverse the tree and maintain a path list. Whenever we reach a leaf node, we would store the full path. After collecting all root-to-leaf paths, we would iterate over them and compute their sums, selecting only the ones that equal targetSum.

This approach works because it exhaustively checks every possible root-to-leaf path. Since every valid answer must appear in this collection, correctness is guaranteed.

However, it performs unnecessary work. We store paths even if they obviously will not contribute to the answer, and we repeatedly compute sums after traversal instead of maintaining a running total during recursion.

Optimal Approach, Depth-First Search with Backtracking

The key insight is that we can evaluate path sums while traversing the tree, rather than after collecting every path.

A depth-first search (DFS) naturally fits this problem because we are exploring root-to-leaf paths. During traversal, we maintain:

  • The current path
  • The remaining sum needed to reach targetSum

At each node:

  • Add the current node value to the path.
  • Subtract the node value from the remaining target.
  • If we reach a leaf node and the remaining target becomes zero, we have found a valid path.
  • Backtrack after exploring children by removing the node from the path.

Backtracking is essential because the same path list is reused across recursive calls. Without removing nodes after exploration, sibling branches would incorrectly inherit previous values.

Approach Time Complexity Space Complexity Notes
Brute Force O(N × H) O(N × H) Generates all root-to-leaf paths, then recomputes sums
Optimal O(N) O(H) excluding output DFS computes sums during traversal and backtracks efficiently

Here:

  • N is the number of nodes.
  • H is the tree height.

Algorithm Walkthrough

  1. Start a depth-first traversal from the root node.

We recursively explore the tree because each recursive call naturally represents moving deeper into a path. 2. Maintain a current_path list.

Every time we visit a node, append its value to this list. This tracks the exact sequence of nodes from the root to the current position. 3. Track the remaining target.

Instead of repeatedly summing the path, subtract the current node value from the remaining target sum.

If the original target is 22 and the current node value is 5, the remaining target becomes 17. 4. Check whether the node is a leaf.

A node is a leaf if both left and right are None.

If we are at a leaf and the remaining target equals the node value, then the entire path sum equals targetSum. 5. Save a copy of the path.

We append current_path[:] to the result list.

A copy is necessary because backtracking will later modify current_path. Without copying, all stored results would point to the same mutable list. 6. Recurse into the left and right children.

Continue exploring deeper paths while passing the updated remaining target. 7. Backtrack after recursion.

Remove the current node from current_path using pop().

This restores the state before returning to the parent node, allowing sibling branches to start with the correct path.

Why it works

The algorithm works because DFS explores every root-to-leaf path exactly once. At every recursive step, current_path accurately represents the path from the root to the current node, and the remaining target correctly tracks how much sum is still needed. When a leaf node is reached, a path is added only if the remaining sum condition is satisfied. Backtracking guarantees that state does not leak between sibling branches, ensuring correctness.

Python Solution

# 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]]:
        result = []
        current_path = []

        def dfs(node: Optional[TreeNode], remaining_sum: int) -> None:
            if not node:
                return

            current_path.append(node.val)

            if (
                not node.left
                and not node.right
                and remaining_sum == node.val
            ):
                result.append(current_path[:])
            else:
                dfs(node.left, remaining_sum - node.val)
                dfs(node.right, remaining_sum - node.val)

            current_path.pop()

        dfs(root, targetSum)
        return result

The implementation begins by creating two structures: result, which stores all valid paths, and current_path, which tracks the active traversal path.

The nested dfs() function performs recursive traversal. If the node is None, recursion stops immediately since there is no path to explore.

When visiting a node, its value is appended to current_path. This ensures the path always represents the current root-to-node sequence.

The leaf node condition is particularly important. We only consider a path valid if:

  • The node has no children.
  • The remaining sum exactly equals the node's value.

If both conditions are met, we append a copy of the path to result.

Otherwise, recursion continues into both subtrees with an updated remaining target.

Finally, current_path.pop() performs backtracking. This restores the path to its previous state before returning to the parent call.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) [][]int {
	var result [][]int
	var currentPath []int

	var dfs func(node *TreeNode, remainingSum int)

	dfs = func(node *TreeNode, remainingSum int) {
		if node == nil {
			return
		}

		currentPath = append(currentPath, node.Val)

		if node.Left == nil &&
			node.Right == nil &&
			remainingSum == node.Val {

			pathCopy := make([]int, len(currentPath))
			copy(pathCopy, currentPath)
			result = append(result, pathCopy)
		} else {
			dfs(node.Left, remainingSum-node.Val)
			dfs(node.Right, remainingSum-node.Val)
		}

		currentPath = currentPath[:len(currentPath)-1]
	}

	dfs(root, targetSum)
	return result
}

The Go implementation closely mirrors the Python solution but requires explicit slice handling.

Instead of Python list copying with [:], Go requires allocating a new slice using make() and copying elements using copy(). This is necessary because slices are references to underlying arrays. Without creating a copy, later backtracking modifications would affect stored paths.

Go also uses nil checks for missing nodes, which corresponds to Python's None.

Integer overflow is not a concern here because the constraints remain comfortably within Go's integer range.

Worked Examples

Example 1

Input

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

The traversal proceeds as follows:

Current Node Current Path Remaining Sum Before Visit Remaining Sum After Visit Action
5 [5] 22 17 Continue
4 [5,4] 17 13 Continue
11 [5,4,11] 13 2 Continue
7 [5,4,11,7] 2 -5 Leaf, invalid
2 [5,4,11,2] 2 0 Valid path
8 [5,8] 17 9 Continue
13 [5,8,13] 9 -4 Leaf, invalid
4 [5,8,4] 9 5 Continue
5 [5,8,4,5] 5 0 Valid path
1 [5,8,4,1] 5 4 Leaf, invalid

Final result:

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

Example 2

Input

root = [1,2,3]
targetSum = 5
Current Node Current Path Remaining Sum
1 [1] 4
2 [1,2] 2
3 [1,3] 1

Neither leaf node satisfies the required sum.

Final result:

[]

Example 3

Input

root = [1,2]
targetSum = 0
Current Node Current Path Remaining Sum
1 [1] -1
2 [1,2] -3

No valid path exists.

Final result:

[]

Complexity Analysis

Measure Complexity Explanation
Time O(N) Every node is visited exactly once
Space O(H) Recursive call stack and path storage proportional to tree height, excluding output

The DFS traversal touches each node only once, making the time complexity linear in the number of nodes.

The auxiliary space complexity is O(H) because recursion depth and current_path both depend on tree height. In the worst case of a skewed tree, this becomes O(N). The output list itself is not counted in auxiliary space since it is required by the problem.

Test Cases

# Helper TreeNode class for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

solution = Solution()

# Example 1
root1 = TreeNode(
    5,
    TreeNode(
        4,
        TreeNode(
            11,
            TreeNode(7),
            TreeNode(2)
        )
    ),
    TreeNode(
        8,
        TreeNode(13),
        TreeNode(
            4,
            TreeNode(5),
            TreeNode(1)
        )
    )
)
assert solution.pathSum(root1, 22) == [
    [5, 4, 11, 2],
    [5, 8, 4, 5]
]  # multiple valid paths

# Example 2
root2 = TreeNode(1, TreeNode(2), TreeNode(3))
assert solution.pathSum(root2, 5) == []  # no valid path

# Example 3
root3 = TreeNode(1, TreeNode(2))
assert solution.pathSum(root3, 0) == []  # impossible target

# Empty tree
assert solution.pathSum(None, 10) == []  # no nodes

# Single node valid
root4 = TreeNode(5)
assert solution.pathSum(root4, 5) == [[5]]  # root equals target

# Single node invalid
root5 = TreeNode(5)
assert solution.pathSum(root5, 10) == []  # root does not match target

# Negative values
root6 = TreeNode(
    -2,
    None,
    TreeNode(-3)
)
assert solution.pathSum(root6, -5) == [
    [-2, -3]
]  # negative numbers

# Multiple overlapping paths
root7 = TreeNode(
    1,
    TreeNode(2, TreeNode(3)),
    TreeNode(2, None, TreeNode(3))
)
assert solution.pathSum(root7, 6) == [
    [1, 2, 3],
    [1, 2, 3]
]  # duplicate valid paths

# Deep skewed tree
root8 = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(
            3,
            TreeNode(4)
        )
    )
)
assert solution.pathSum(root8, 10) == [
    [1, 2, 3, 4]
]  # skewed tree path
Test Why
Example 1 Verifies multiple valid paths
Example 2 Verifies no valid path exists
Example 3 Checks impossible target
Empty tree Ensures None input works
Single node valid Root is also a leaf
Single node invalid Leaf path does not match target
Negative values Confirms negative sums are handled correctly
Duplicate paths Ensures independent path storage
Deep skewed tree Tests recursion depth and single-path traversal

Edge Cases

Empty Tree

An empty tree (root = None) is a common source of bugs because recursion may attempt to access properties on a null object. Our implementation immediately returns from DFS when encountering None, which naturally produces an empty result list.

Single Node Tree

When the tree contains only one node, the root is also a leaf. A naive implementation might forget to treat this as a complete path. Our leaf condition explicitly checks whether both children are missing, ensuring single-node trees are handled correctly.

Negative Node Values

Because node values may be negative, early pruning is unsafe. For example, a path sum may temporarily exceed the target and later decrease due to negative numbers. Our implementation avoids incorrect pruning entirely and explores all root-to-leaf paths, guaranteeing correctness.

Mutable Path Bugs

A subtle issue in backtracking problems is accidentally storing references to a mutable path instead of copies. If we appended current_path directly, later pop() operations would modify already stored answers. By saving current_path[:] in Python and using copy() in Go, each result remains independent and correct.