66. Path Sum II

Q: Why check remaining === node.val at the leaf?

We're checking BEFORE subtracting. If we subtract first, we'd check remaining === 0 after subtracting.

Q: Why both children null check?

A 'leaf' is a node with NO children. A node with one child is NOT a leaf — its path continues.

mediumAsked at Datadog

Find all root-to-leaf paths where the sum equals a target. Datadog uses this for backtracking with path tracking — same shape as enumerating valid traces through a service-dependency graph.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Datadog loops.

Glassdoor (2026-Q1)— Datadog onsite — graded on path-tracking backtracking.

Problem

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

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,5,1], targetSum = 22

Output

[[5,4,11,2],[5,8,4,5]]

Example 2

Input

root = [1,2,3], targetSum = 5

Output

[]

Approaches

1. DFS, copy path at each node

Recurse; pass a fresh path array at each level.

Time: O(n^2)
Space: O(n^2)

// Allocates O(n) array per node visit. Total O(n^2) memory.

Tradeoff: Wasteful allocations. Datadog will push for the shared-path approach.

2. DFS with shared path, push/pop (optimal)

Single mutable path. Push on entry, pop on exit. Copy only when emitting a result.

Time: O(n^2) for output, O(n) extra
Space: O(h) recursion + output

function pathSum(root, targetSum) {
  const out = [];
  function dfs(node, remaining, path) {
    if (!node) return;
    path.push(node.val);
    if (!node.left && !node.right && remaining === node.val) {
      out.push([...path]);
    }
    dfs(node.left, remaining - node.val, path);
    dfs(node.right, remaining - node.val, path);
    path.pop();
  }
  dfs(root, targetSum, []);
  return out;
}

Tradeoff: O(h) extra space (path + recursion). Copying only at emit keeps the inner loop tight. Datadog-canonical.

Datadog-specific tips

Datadog grades on whether you use the shared-mutable-path with push/pop (the canonical backtracking idiom). They'll also check that you only emit when BOTH children are null (true leaf condition) — not when one is null.

Common mistakes

Emitting at internal nodes — produces incorrect 'partial' paths.
Forgetting to pop after recursion — corrupts subsequent siblings.
Comparing remaining === 0 instead of remaining === node.val on the last node — off by one.

Follow-up questions

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

Path Sum (LC 112) — just existence check.
Path Sum III (LC 437) — any-node-to-any-node paths.
Datadog-style: enumerate root-to-leaf traces with a budget constraint.

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 check remaining === node.val at the leaf?

We're checking BEFORE subtracting. If we subtract first, we'd check remaining === 0 after subtracting.

Why both children null check?

A 'leaf' is a node with NO children. A node with one child is NOT a leaf — its path continues.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →