Skip to main content

14. Path Sum

easyAsked at Coursera

Check whether a root-to-leaf path summing to a target exists, a DFS problem Coursera uses to test tree traversal for prerequisite-chain checks.

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 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 (enumerate all paths)

Collect all root-to-leaf paths, then check if any sums to targetSum — extra O(n) space for path storage.

Time
O(n)
Space
O(n)
// Build all paths then sum each — wasteful
function hasPathSum(root, target) {
  if (!root) return false;
  const paths = [];
  function dfs(node, path) {
    if (!node.left && !node.right) { paths.push([...path, node.val]); return; }
    if (node.left) dfs(node.left, [...path, node.val]);
    if (node.right) dfs(node.right, [...path, node.val]);
  }
  dfs(root, []);
  return paths.some(p => p.reduce((a,b) => a+b, 0) === target);
}

Tradeoff:

2. DFS with running sum

Subtract each node's value from targetSum as we recurse; return true when a leaf reduces it to zero. Single pass, O(h) space.

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:

Coursera-specific tips

Coursera interviews emphasize algorithms for educational platforms, content recommendation systems, and scalable delivery pipelines. Medium-difficulty graph and DP problems are typical.

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 Coursera interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →