Skip to main content

14. Path Sum

easyAsked at DigitalOcean

Check if a root-to-leaf path sums to a target — a foundational DFS pattern DigitalOcean uses to evaluate recursive thinking and edge case awareness.

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

DFS to collect every root-to-leaf path sum into an array, then check if target is in the array.

Time
O(n)
Space
O(n)
function hasPathSum(root, target) {
  const sums = [];
  function dfs(node, cur) {
    if (!node) return;
    cur += node.val;
    if (!node.left && !node.right) sums.push(cur);
    dfs(node.left, cur);
    dfs(node.right, cur);
  }
  dfs(root, 0);
  return sums.includes(target);
}

Tradeoff:

2. Recursive DFS with remaining sum

Subtract current node value from target and recurse; at a leaf, check if remainder is zero. Short-circuits as soon as a valid path is found.

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:

DigitalOcean-specific tips

DigitalOcean values clean termination conditions — make sure your base cases handle empty trees and single-node trees explicitly before the interviewer asks.

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

Practice these live with InterviewChamp.AI →