Skip to main content

15. Path Sum

easyAsked at Udemy

Check if a root-to-leaf path sums to a target — Udemy uses this as a gateway to harder path-aggregation problems in recommendation scoring.

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

  • 0 <= number of nodes <= 5000
  • -1000 <= Node.val, 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 root-to-leaf paths and check each sum.

Time
O(n)
Space
O(n)
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:

2. Recursive subtraction DFS

Subtract each node's value from remaining target as you descend; return true when a leaf hits 0.

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

Tradeoff:

Udemy-specific tips

Udemy asks about e-learning recommendation systems, content search, and marketplace algorithms — balanced mix of arrays, hash maps, and dynamic programming problems.

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

Practice these live with InterviewChamp.AI →