Skip to main content

15. Path Sum

easyAsked at Workday

Given a binary tree and a target sum, determine if there's a root-to-leaf path summing to the target. Workday uses this to evaluate accumulator-passing in recursion — analogous to summing payroll items along an approval chain.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 phone screen.

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

Example 2

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

Example 3

Input
root = [], targetSum = 0
Output
false

Approaches

1. Enumerate all root-to-leaf paths

Collect every path, then sum each and check.

Time
O(n^2) worst case
Space
O(n^2)
// build list of paths, then for each path compute sum
// O(n) paths * O(n) sum each

Tradeoff: Wasteful — we don't need the paths, only the sum check.

2. DFS with remaining target

Subtract node value from remaining target as you descend. At a leaf, check if remaining == 0.

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

Tradeoff: Subtracting from target avoids passing a running sum — cleaner. Leaf check is the gate.

Workday-specific tips

Workday grades the leaf check: a node with one child is NOT a leaf, so don't return true at internal nodes. Empty tree returns false even if target is 0 (no path exists in an empty tree). Mention the approval-chain analogy.

Common mistakes

  • Returning true at any node where remain == 0 — must be at a leaf.
  • Treating a node with one null child as a leaf — it has one real child, so recurse.
  • Returning true on empty tree when target is 0 — there's no path at all.

Follow-up questions

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

  • Path Sum II (LC 113) — return all paths.
  • Path Sum III (LC 437) — any node to any descendant.
  • Sum Root to Leaf Numbers (LC 129).

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 subtract instead of accumulate?

Same logic, but subtracting is one variable per recursive call instead of needing to pass both running sum and target. Slightly less to remember.

What counts as a leaf?

Both children null. A node with one child is not a leaf.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →