Skip to main content

10. Path Sum

easyAsked at Notion

Determine whether a root-to-leaf path sums to a target. Notion uses this as a base case before extending to tree-aggregate problems.

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

Source citations

Public interview reports confirming this problem appears in Notion loops.

  • Glassdoor (2026-Q1)— Notion uses this as an entry to Path Sum II and III.
  • LeetCode Discuss (2025-11)— Reported in Notion phone screen tree round.

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

Example 3

Input
root = [], targetSum = 0
Output
false

Approaches

1. DFS, collect all root-to-leaf sums

Enumerate every root-to-leaf path, sum each, check membership.

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

Tradeoff: Correct but materializes every path sum. No early exit.

2. DFS with running target subtraction (optimal)

Pass remaining target down the tree. At each leaf check if remaining == node.val.

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

Tradeoff: Short-circuits at the first matching leaf. No accumulator needed beyond the parameter.

Notion-specific tips

Notion grades the leaf detection: many candidates check 'is null' and incorrectly count internal nodes with one child as leaves. State that 'leaf = both children are null' before coding.

Common mistakes

  • Treating internal nodes with one null child as leaves — answers diverge.
  • Returning false on null root for non-empty target — only correct because the constraint says we must hit a leaf.
  • Not subtracting node.val from target — the running sum gets wrong.

Follow-up questions

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

  • Path Sum II (LC 113) — return all matching paths.
  • Path Sum III (LC 437) — any path, not just root-to-leaf.
  • What if the tree has negative values? (Already covered by constraints.)

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

What about the empty tree?

Return false. An empty tree has no leaves, so no root-to-leaf path sums to anything.

Does a single-node tree with val == target return true?

Yes — a single node is its own leaf, and the path sum equals its value.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →