Skip to main content

13. Path Sum

easyAsked at PayPal

Determine whether a binary tree has a root-to-leaf path whose node values sum to a given target. PayPal uses this to test recursive tree traversal and base-case handling under financial-rule evaluation scenarios.

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

Source citations

Public interview reports confirming this problem appears in PayPal loops.

  • Glassdoor (2025)— PayPal SWE intern reported a tree path-sum variant during phone screen
  • LeetCode Discuss (2026)— Thread confirming PayPal asks tree DFS problems in early rounds

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

  • Number of nodes 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 (enumerate all paths)

Generate all root-to-leaf paths, compute each sum, compare to target.

Time
O(n)
Space
O(n)
// collect all paths then check sums
function hasPathSum(root, target) {
  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) === target);
}

Tradeoff: Stores all paths unnecessarily; extra memory for no gain.

2. Recursive DFS with running remainder

Subtract each node's value from the target as we descend. At a leaf, check if the remainder equals zero. This avoids storing paths and terminates early on mismatch.

Time
O(n)
Space
O(h) where h is tree height
function hasPathSum(root, targetSum) {
  if (!root) return false;
  // At a leaf, check if this node's value equals the remaining target
  if (!root.left && !root.right) {
    return root.val === targetSum;
  }
  const remaining = targetSum - root.val;
  return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
}

Tradeoff: Clean O(h) space recursion; short-circuits on first valid path found.

PayPal-specific tips

PayPal interviews focus on payment processing, fraud detection logic, financial reconciliation algorithms, and distributed transaction design. Hash maps, sliding windows, and two-pointer techniques appear frequently.

Common mistakes

  • Returning true when root is null instead of false — empty tree has no root-to-leaf path
  • Checking sum at every node instead of only at leaves, causing false positives on internal nodes
  • Forgetting to subtract node.val before recursing, comparing raw target at the leaf

Follow-up questions

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

  • Return all root-to-leaf paths that sum to the target (LC 113 Path Sum II)
  • Find the maximum root-to-leaf path sum in the tree
  • Solve with iterative DFS using an explicit stack

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

What if the tree has only one node?

That single node is both root and leaf. Return true if its value equals targetSum, false otherwise.

Does the path have to start at the root?

Yes — the problem specifies root-to-leaf paths only. For arbitrary paths see Path Sum III (LC 437).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →