easy

Path Sum

Check whether a binary tree has a root-to-leaf path that adds up to a target sum.

1. Define the problem

Path Sum

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that the values along the path add up to targetSum. Use depth-first search , subtracting each node's value from the running target as you descend. At a leaf , the path matches if what remains of the target equals the leaf's own value.

Constraints

  • The number of nodes in the tree is in the range [0, 5000]
  • -1000 ≤ Node.val ≤ 1000
  • -1000 ≤ targetSum ≤ 1000

Example

Inputroot = [5,4,8,11,null,13,4], targetSum = 20
Outputtrue

Explanation The path 5 → 4 → 11 sums to 20.

2. Know the words first

In plain terms

Root-to-leaf path
The sequence of nodes from the root down to a leaf, following exactly one child at each step.
3. Visualize the solution

Subtract on the way down, check the total at each leaf

Subtract on the way down, check the total at each leaf
Statusvisit 5

remaining = 20 − 5 = 15.

What happens in this step

node 5 (index 0), remaining = 20

Not a leaf (has both children) → remaining -= node.val
remaining = 20 - 5 = 15

Since node 5 has children, its value isn't compared directly — it's subtracted from the running target, and the search continues into dfs(left, 15) first.
Step 1 of 4

Steps to visualize

  1. Carry a running "remaining" value, starting at targetSum.
  2. Before recursing into a node's children, subtract that node's own value from remaining.
  3. At a leaf, compare remaining to the leaf's value — a match means this path sums to targetSum.
  4. If neither child finds a match, backtrack and try the other branch.
  5. An empty tree has no leaf, so it can never match.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Subtract on the way down, check the total at each leaf
Statusvisit 5

remaining = 20 − 5 = 15.

What happens in this step

node 5 (index 0), remaining = 20

Not a leaf (has both children) → remaining -= node.val
remaining = 20 - 5 = 15

Since node 5 has children, its value isn't compared directly — it's subtracted from the running target, and the search continues into dfs(left, 15) first.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function hasPathSum(values, targetSum) {
  function buildTree(arr) {
    if (!arr || arr.length === 0 || arr[0] === null) return null;

    const root = { val: arr[0], left: null, right: null };
    const queue = [root];
    let i = 1;

    while (queue.length > 0 && i < arr.length) {
      const node = queue.shift();

      if (i < arr.length) {
        const leftVal = arr[i++];
        if (leftVal !== null && leftVal !== undefined) {
          node.left = { val: leftVal, left: null, right: null };
          queue.push(node.left);
        }
      }
      if (i < arr.length) {
        const rightVal = arr[i++];
        if (rightVal !== null && rightVal !== undefined) {
          node.right = { val: rightVal, left: null, right: null };
          queue.push(node.right);
        }
      }
    }

    return root;
  }

  function dfs(node, remaining) {
    if (!node) return false;
    if (!node.left && !node.right) return remaining === node.val;

    remaining -= node.val;
    return dfs(node.left, remaining) || dfs(node.right, remaining);
  }

  return dfs(buildTree(values), targetSum);
}
Time
O(n)
Space
O(h) — h is the height of the tree, for the recursion stack
6. Test cases

Test cases

InputExpectedCovers
root = [5,4,8,11,null,13,4], targetSum = 20trueexample from the docstring
root = [5,4,8,11,null,13,4], targetSum = 27falsetarget does not match any root-to-leaf sum
root = [], targetSum = 0falsean empty tree has no leaf, so it never matches, even for 0
root = [5], targetSum = 5truesmallest valid tree, root is also the matching leaf
root = [5], targetSum = 3falsesingle node whose value does not equal the target
root = [-2,null,-3], targetSum = -5truenegative node values summing correctly
root = [1,2], targetSum = 1falsethe target matches a non-leaf node, which does not count
root = [1,2,3], targetSum = 4truethe matching path is on the second branch tried

Keep reading