MediumBacktrackingTreeDepth-First SearchBinary Tree

Path Sum II

1 approach, code in every language

You are given the root of a binary tree together with an integer targetSum. A root-to-leaf path is a sequence of nodes that begins at the root and ends at a leaf, moving only from a parent to one of its children.

Return every root-to-leaf path whose node values add up exactly to targetSum. Each qualifying path should be returned as the list of node values encountered along the way, and the paths themselves may be returned in any order.

A leaf is a node that has no children. If no path reaches the target, return an empty list.

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]]

Two root-to-leaf paths sum to 22: 5 -> 4 -> 11 -> 2 and 5 -> 8 -> 4 -> 5.

Example 2

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

Output: []

The root-to-leaf paths sum to 3 (1 -> 2) and 4 (1 -> 3); neither reaches 5.

Constraints

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

DFS with Backtracking

Walk every root-to-leaf path while tracking the running total, recording a copy of the path whenever it lands on the target at a leaf.

Loading animation…

Intuition

Because a valid answer must be an entire root-to-leaf path, we can explore the tree depth-first and keep the list of values seen so far. Instead of recomputing sums, we subtract each node's value from the remaining target as we descend, so a match is simply the remaining target hitting zero at a leaf. The one subtlety is that the path list is shared across the whole traversal, so when we find a winning path we must store a copy rather than a reference. After visiting a node's children we pop that node from the path, restoring the state for the sibling branch. This push-explore-pop rhythm is classic backtracking and keeps the extra memory proportional to the tree height.

Algorithm walkthrough

1Maintain a mutable path list and a results list; start the DFS from the root with remaining = targetSum.
2On entering a node, append its value to path and subtract its value from remaining.
3If the node is a leaf and remaining is now zero, push a copy of path into results.
4Otherwise recurse into the left child and the right child with the updated remaining value.
5Before returning, pop the current node's value from path so sibling branches see a clean state.
6After the traversal completes, return the results list.

Implementation

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        result: List[List[int]] = []
        path: List[int] = []

        def dfs(node: Optional[TreeNode], remaining: int) -> None:
            if not node:
                return
            path.append(node.val)
            remaining -= node.val
            if not node.left and not node.right and remaining == 0:
                result.append(list(path))
            else:
                dfs(node.left, remaining)
                dfs(node.right, remaining)
            path.pop()

        dfs(root, targetSum)
        return result

Time

O(n^2)

Space

O(n)

Visiting every node is O(n), but copying a matching path can cost O(n); in the worst case (a balanced tree with many full-length matches) the copies dominate at O(n^2). Space is the recursion depth plus the path list, both O(n) in a skewed tree, excluding the output.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Ridge Descents Matching a Drop is our own problem on the technique behind Path Sum II: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free