Skip to main content

14. Path Sum

easyAsked at Snowflake

Determine whether a root-to-leaf path sums to a target. Snowflake asks this to test recursion with a target accumulator — relevant for plan-cost rollup where each operator adds cost on the way up.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler team uses this to set up plan-cost discussion.
  • LeetCode Discuss (2025-10)— Reported at Snowflake new-grad screens.

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

  • The number of nodes in the tree 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

Example 2

Input
root = [1,2,3], targetSum = 5
Output
false

Approaches

1. Enumerate all root-to-leaf paths

DFS collecting each full path, then sum each and check.

Time
O(n) per path, O(n^2) total in worst case
Space
O(n)
function hasPathSum(root, targetSum) {
  if (!root) return false;
  const paths = [];
  function dfs(n, path) {
    if (!n) return;
    path.push(n.val);
    if (!n.left && !n.right) paths.push([...path]);
    dfs(n.left, path);
    dfs(n.right, path);
    path.pop();
  }
  dfs(root, []);
  return paths.some(p => p.reduce((a, b) => a + b, 0) === targetSum);
}

Tradeoff: Materializes every path. Don't ship for big trees.

2. Subtract on the way down (optimal)

Recurse passing targetSum - node.val. At a leaf, return targetSum === node.val.

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

Tradeoff: Linear, short-circuits. No path materialization.

Snowflake-specific tips

Snowflake interviewers want the subtract-on-the-way-down pattern because it eliminates the need to track the running sum. Bonus signal: discuss how plan-cost rollup works in their planner — each operator adds its own cost as the planner descends the plan tree.

Common mistakes

  • Treating a null child as a leaf — only nodes with both children null are leaves.
  • Returning true at root if root.val == targetSum, ignoring that root might have children.
  • Forgetting the early null check — passing null root and target 0 should return false.

Follow-up questions

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

  • Path Sum II (LC 113) — return all paths, not just yes/no.
  • Path Sum III (LC 437) — any path, not just root-to-leaf.
  • How does Snowflake compute cumulative plan cost during enumeration?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why is null-leaf an empty subtree, not a leaf?

A 'leaf' must be a node. If you treat null as a leaf, you double-count paths through single-child internal nodes. The definition: leaf = node with both children null.

How does this relate to plan costing?

When Snowflake's planner enumerates physical plans, it walks the plan tree and accumulates cost on the way down. At each leaf (a scan operator), it checks whether the cumulative cost beats the best-so-far — same shape as Path Sum.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →