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 Sam K., 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.

More ServiceNow coding interview questions

See all ServiceNow problems →

Companies that also ask Path Sum