Skip to main content

15. Path Sum

easyAsked at Spotify

Determine if the tree has a root-to-leaf path that sums to a target.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path where the sum of values along the path equals targetSum.

Constraints

  • 0 <= nodes <= 5000
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

Examples

Example 1

Input
root=[5,4,8,11,null,13,4,7,2,null,null,null,1], target=22
Output
true

Example 2

Input
root=[1,2,3], target=5
Output
false

Approaches

1. Enumerate all paths

Generate every root-to-leaf list of values, then check sums

Time
O(n^2)
Space
O(n^2)
// build all path arrays, sum each, compare to target — wastes both time and memory

Tradeoff:

2. DFS with remaining sum

Subtract node value from the remaining target. Leaf hits when remaining equals leaf's value.

Time
O(n)
Space
O(h)
function hasPathSum(root, target) {
  if (!root) return false;
  if (!root.left && !root.right) return target === root.val;
  return hasPathSum(root.left, target - root.val)
      || hasPathSum(root.right, target - root.val);
}

Tradeoff:

Spotify-specific tips

Spotify uses sum-along-path patterns when computing aggregated listen-counts up a genre tree, so naming the recurrence in plain English earns bonus signal.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Spotify coding interview questions

See all Spotify problems →

Companies that also ask Path Sum