Skip to main content

113. Path Sum II

medium

Return every root-to-leaf path whose values sum to a target. Tree DFS with a path accumulator — the standard recursion pattern for enumerating paths in a binary tree.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references. A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Constraints

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

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

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

Example 2

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

Example 3

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

DFS from root with a current path and current sum.

Hint 2

On entering a node, push its value and subtract its value from the remaining target.

Hint 3

Leaf check: !node.left and !node.right. If the remaining target hits 0 at a leaf, snapshot the path.

Hint 4

Pop the node value on the way out (backtrack).

Solution approach

Reveal approach

Standard DFS with backtracking. dfs(node, remaining, path): if node is null, return. Append node.val to path; subtract node.val from remaining. If node is a leaf (no children) and remaining == 0, snapshot path to result. Otherwise recurse into left and right children. Pop node.val from path on the way out (backtrack so the path doesn't leak into sibling branches). Time is O(n) for traversing the tree plus O(n) per result for path copying — worst case O(n^2) when many leaves match. Space is O(h) recursion depth, where h is tree height.

Complexity

Time
O(n^2) worst case
Space
O(h)

Related patterns

  • recursion
  • dfs
  • backtracking
  • tree-traversal

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Path Sum II and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →