Limited Time Offer:Up to 20% off Hello Interview Premium

⌘K

Tutor

Depth-First Search

Path Sum II

medium

DESCRIPTION (inspired by Leetcode.com)

Given the root of a binary tree and an integer target, write a recursive function to find all root-to-leaf paths where the sum of all the values along the path sum to target.

Example 1:

Input:

[1,2,4,4,7,5,1]
target = 10

Output:

[[1,2,7],[1,4,5]] # [[1,4,5],[1,2,7]] is also accepted.

The paths are 1 -> 2 -> 7 and 1 -> 4 -> 5

Explanation

This problem is an extension of the Path Sum problem. In this problem, we are asked to return a list of all root-to-leaf paths where the sum of the nodes in the path equals a given target sum.

This is an example of a question which benefits from using a global variable that all recursive calls have access to store the list of all root-to-leaf paths that match the target sum.

Return Values In this case question, we don't need our recursive calls to return any values. Instead, we use depth-first search to traverse each root-to-leaf path in the tree, while maintaining the state of the current path via parameters to the recursive call.

Base Case We can stop recursing when our tree is empty.

Extra Work At each node, we need to add the value of the node to the current path.

Whenever we are at a leaf node, we can check if the value of the current node matches the target. If it does, we can add the current path to the global list of paths.

Helper Function Parent nodes need to pass two pieces of information down to their children:

The remaining target sum
The values along the current path (starting from the root).

These values must be passed down as parameters of the recursive call, so we need to introduce a helper function to help us recurse.

Global Variables We will use a global variable to store the root-to-leaf paths that match the given target. This allows us to avoid having to return path arrays up the recursion stack and simplifies collecting all valid paths.

Solution

def dfs(node, target, path):
    # base case
    if not node:
        return
    # append current value to the path
    path.append(node.val)
    if not node.left and not node.right:
        if node.val == target:
            result.append(path[:])
    dfs(node.left, target - node.val, path)
    dfs(node.right, target - node.val, path)
    # when our code reaches here, are done exploring all
    # the root-to-leaf paths that go through the current node.
    # pop the current value from the path to prepare for the next path
    path.pop()

Global Variables We can use a single global variable that all recursive calls have access to store the list of paths that add up to the target sum.

Solution

class Solution:
    def pathSum(self, root, target):
        def dfs(node, target, path):
            # base case
            if not node:
                return
            # append current value to the path
            path.append(node.val)
            if not node.left and not node.right:
                if node.val == target:
                    result.append(path[:])
            dfs(node.left, target - node.val, path)
            dfs(node.right, target - node.val, path)
            # when our code reaches here, are done exploring all
            # the root-to-leaf paths that go through the current node.
            # pop the current value from the path to prepare for the next path
            path.pop()
        result = []
        dfs(root, target, [])
        return result

Animated Solution

Visualization

Try these examples:


def pathSum(root, target):
  def dfs(node, target, path):
    if not node:
      return
    
    path.append(node.val)
    if not node.left and not node.right:
      if node.val == target:
        result.append(path[:])
    
    dfs(node.left, target - node.val, path)
    dfs(node.right, target - node.val, path)
    path.pop()
  result = []
  dfs(root, target, [])
  return result

path sum II

0 / 41

Test Your Knowledge

Complexity Analysis

Time Complexity: O(N²) where N is the number of nodes in the binary tree. We visit each node exactly once, which is O(N). However, when we find a valid root-to-leaf path, we copy it into the result list, which costs up to O(H) where H is the tree height. With K valid paths, the total copy cost is O(K·H), giving us O(N + K·H) overall. In the worst case: a 'caterpillar' tree where a long spine of N/2 nodes each has a leaf child — both K and H are O(N), so this becomes O(N²). Note that a fully balanced tree gives O(N·log N) since H = log N, and a fully skewed tree (a straight chain) gives O(N) since K = 1. The O(N²) worst case comes from tree shapes in between these extremes.

Space Complexity: O(N²) where N is the number of nodes in the binary tree in the worst case. The recursion stack uses O(H) space and the current path list uses O(H) space where H is the tree height. The result stores K valid paths of up to length H, which is O(K·H). In the worst case: the same 'caterpillar' tree shape would total to O(N²).

Mark as read

Next: Longest Univalue Path

Your account is free and you can post anonymously if you choose.

Unlock Premium Coding Content

Interactive algorithm visualizations

Guided Practice

Recent interview questions

Learn More

Reading Progress

On This Page

Explanation

Solution

Animated Solution

Depth-First Search

Path Sum II

DESCRIPTION (inspired by Leetcode.com)

Explanation

Solution

Animated Solution

Test Your Knowledge

Complexity Analysis

Comments

Questions

Learn

Links

Legal

Contact