Skip to main content

13. Path Sum

easyAsked at Adobe

Determine if a binary tree has a root-to-leaf path whose node values sum to a given target. Adobe uses this to test recursive DFS reasoning and the candidate's ability to propagate state down a tree — skills central to traversing document and scene graph hierarchies.

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

Source citations

Public interview reports confirming this problem appears in Adobe loops.

  • Blind (2025-12)— Adobe SDE-I candidates report recursive tree path problems appearing in phone screens.
  • LeetCode Discuss (2026-02)— Adobe interviewers cite tree path problems as a standard progression from depth questions.

Problem

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. 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,null,1], targetSum = 22
Output
true

Explanation: Path 5 -> 4 -> 11 -> 2 sums to 22.

Example 2

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

Approaches

1. Brute force — collect all paths

DFS collecting all root-to-leaf paths, then check if any path sum equals targetSum.

Time
O(n)
Space
O(n)
function hasPathSum(root, targetSum) {
  const paths = [];
  function dfs(node, path) {
    if (!node) return;
    path.push(node.val);
    if (!node.left && !node.right) paths.push([...path]);
    dfs(node.left, path);
    dfs(node.right, path);
    path.pop();
  }
  dfs(root, []);
  return paths.some(p => p.reduce((a, b) => a + b, 0) === targetSum);
}

Tradeoff: Correct but stores all paths in memory; wasteful since we only need a boolean.

2. DFS with running remainder

Instead of tracking the running sum, subtract the current node's value from targetSum as you recurse. At a leaf, check if the remainder equals zero. This avoids any extra storage.

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

Tradeoff: Clean O(h) space recursion. The subtraction trick is the key insight Adobe interviewers look for — it eliminates the need to track an accumulator array.

Adobe-specific tips

Adobe values the 'remainder propagation' pattern because it maps directly to accumulator reduction in pipeline stages (e.g., computing cumulative transforms through a scene graph). Be ready to extend this to 'Path Sum II' (print all paths) and discuss how to handle negative node values which can cause paths to look unpromising before becoming valid.

Common mistakes

  • Returning false when root is null without checking — null root with targetSum=0 should still return false (no leaf exists).
  • Checking the remainder at every node, not just leaves — interior node values can be arbitrary.
  • Short-circuit bug: using 'and' instead of 'or' when combining left and right results.

Follow-up questions

An interviewer at Adobe may pivot to one of these next:

  • Path Sum II (LC 113): return all root-to-leaf paths that sum to targetSum.
  • Path Sum III (LC 437): count paths that sum to target, not necessarily root-to-leaf.
  • How would you implement this iteratively using a stack that stores (node, remainingSum) pairs?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why check the remainder at a leaf, not any node?

The problem specifies root-to-leaf paths. An interior node with the right partial sum does not constitute a valid path. Always confirm both left and right children are null before checking.

Does this work with negative values?

Yes — the DFS explores all root-to-leaf paths regardless of partial sums, so negative values do not cause early termination of valid paths.

Practice these live with InterviewChamp.AI

Drill Path Sum and other Adobe interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →