Skip to main content

14. Path Sum

easyAsked at Chegg

Check if a root-to-leaf path sums to a target — a foundational tree traversal problem Chegg uses to assess recursion and path-tracking skills.

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

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 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

Approaches

1. Brute force

Generate all root-to-leaf paths, compute each sum, 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:

2. Recursive subtraction

Subtract each node's value from the target as you descend; at a leaf, check if the remainder is zero. This avoids building path arrays entirely.

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

Tradeoff:

Chegg-specific tips

Chegg expects you to handle the empty-tree edge case explicitly and to recognize that both subtrees need checking — rushing to return early on the first found path is a common mistake they probe.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →