Faangprep Logo
Log inStart free
Browse curriculum

Path Sum

Determine if the tree has a root-to-leaf path summing to a target.

EasySolve on LeetCode

Examples

Input:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output:true
Explain:

The path 5 -> 4 -> 11 -> 2 sums to 22.

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

Paths are 1->2 (3) and 1->3 (4). No path sums to 5.

Problem Understanding

Return true when some path that starts at root and ends at a leaf has node values adding up to exactly targetSum. The path must run all the way down: stopping at an inner node does not count, which is what makes this a root-to-leaf check.

A leaf is a node with no children.

Algorithm Strategy (Top-Down State)

We use Pre-order DFS (Top-Down) logic.

Instead of calculating the sum from scratch at every leaf, we subtract the current node's value from the targetSum as we go down.

  1. Consume Value: remaining = target - node.val.
  2. Check Leaf: If node is a leaf (no left, no right) AND remaining == 0, we found a path! Return true.
  3. Recurse: Check dfs(node.left, remaining) OR dfs(node.right, remaining). If either returns true, propagate it up.
  4. Base Case: If node is null, return false.

Interactive Visualization

Each node subtracts its value from what is still needed, and the remainder appears under it. A leaf that reaches exactly 0 turns green. Once a path is found, || stops, so the right side of that node is never called.

Dry Run: Target = 22

Node Current Target Value to Subtract Remaining Needed Action
5 (Root) 22 5 17 Recurse Left (Target 17)
4 17 4 13 Recurse Left (Target 13)
11 13 11 2 Recurse Right (Target 2)
2 (Leaf) 2 2 0 Success! Return True

Edge Cases & Common Mistakes

  • Null Root: Return false (no path exists).
  • Negative Values: The logic works fine with negatives (remaining can increase).
  • Path stops before leaf: e.g. path matches sum but node has children. This is NOT a root-to-leaf path. Must strictly check !left && !right.

Solution

Recursive check for path existence.

Path Sum Code
1var hasPathSum = function(root, targetSum) {
2    if (!root) return false;
3    targetSum -= root.val;
4    if (!root.left && !root.right) {
5        return targetSum === 0;
6    }
7    return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
8};
Previous

Maximum Depth of Binary Tree

Next

Passing Values Down (State)

The approach, step by step

  1. Subtract the node

    At each node, subtract its value from the target.

  2. Check at a leaf

    If the node has no children, return whether the remainder is 0.

  3. Try both sides

    Otherwise return left OR right; the right side is skipped once the left finds a path.

Frequently asked questions

Why subtract instead of adding up the path?

Subtracting each node’s value from the target leaves exactly what the rest of the path must add up to. At a leaf you only have to check whether that remainder is 0.

Why does the path have to end at a leaf?

The problem asks for root-to-leaf paths. A node whose running sum already matches but still has children does not count, so the check happens only when both children are empty.

Does it work with negative values?

Yes. Negative values can make the remainder grow again, which is why the search never stops early just because the sum went past the target.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description