Skip to main content

13. Path Sum

easyAsked at ServiceNow

Determine if a binary tree has a root-to-leaf path whose node values sum to a target. ServiceNow favors this to test recursive tree traversal under a constraint, which mirrors how their workflow engine evaluates cumulative cost thresholds in approval chains.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

  • Blind (2025)— Mentioned as a ServiceNow mid-loop tree warm-up.
  • LeetCode Discuss (2026)— Reported alongside tree-traversal questions in ServiceNow SDE-II onsite.

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 root-to-leaf paths

DFS to enumerate every root-to-leaf path, sum each, and check against target.

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. Returns after full traversal rather than short-circuiting on first match.

2. Recursive subtraction DFS

Subtract each node's value from targetSum as you descend. At a leaf, check if the remaining target equals zero. This early-exits on the first matching path and avoids storing paths.

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

Tradeoff: O(h) stack, short-circuits on first found path. The leaf check — both children null — is the critical detail; missing it causes false positives on single-child nodes.

ServiceNow-specific tips

ServiceNow engineers want to see you nail the leaf-node check (both children null) before writing a line — it's the gotcha that separates candidates who reason about trees from those who pattern-match. Bonus signal: extend the problem verbally to 'sum of all root-to-leaf paths' as a follow-up, referencing how ServiceNow SLA calculations aggregate costs across workflow branches.

Common mistakes

  • Treating any node with val == targetSum as a match, instead of checking only leaf nodes.
  • Returning true on a node that has one null child (half-leaf) — the leaf condition requires BOTH children to be null.
  • Forgetting to handle the empty tree (root === null returns false, not true).

Follow-up questions

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

  • Path Sum II: return all root-to-leaf paths that equal the target.
  • Path Sum III: count paths (not necessarily root-to-leaf) that sum to target using prefix sums.
  • Max path sum between any two nodes in the tree (LC 124).

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 does root === null return false instead of targetSum === 0?

Because the problem asks for a root-to-leaf path, and a null node is not a leaf. If target is 0 and the tree is empty, there is no path at all, so false is correct.

Can I use BFS for this?

Yes — push (node, remaining) pairs into a queue and check remaining === 0 at each leaf. It is equally correct and avoids recursion overhead, but slightly more code for the same asymptotic performance.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →