← DSA Atlas
Dedicated problem page · #112

Path Sum

EasyTrees and Binary Search TreesRoot-to-leaf DFS with running targetDepth-first search (recursion)
Solve on LeetCode ↗
112
EasyTrees and Binary Search TreesDepth-first search (recursion)Root-to-leaf DFS with running target

Path Sum

Given the root of a binary tree and an integer targetSum, return true if the tree has at least one root-to-leaf path such that the sum of the node values along the path equals targetSum. A leaf is a node with no children.

Open official problem prompt ↗
In plain English

Decide whether some path from the root down to a leaf has node values that add up exactly to targetSum.

Picture it like this

You start a hike at the summit (root) with a fuel budget. Each trail marker (node) burns some fuel. You succeed only if you arrive at a trail end (leaf) with exactly zero fuel left.

Example
Input
root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output
true
Why
The path 5 -> 4 -> 11 -> 2 sums to 22.
Constraints
The number of nodes is in the range [0, 5000]-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
Pattern lesson

See the pattern, then code

Root-to-leaf DFS with running target
Recognition clue

You must find a path that runs all the way from the root down to a leaf (not any internal stopping point), and you only need a yes/no answer — that is the signature of a subtract-as-you-descend DFS.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. Instead of summing at the end, subtract each node's value from the remaining target as you descend; the answer is true exactly when you reach a leaf and the remaining target equals that leaf's value.

New words, made simpleKnow these before the algorithm
Leaf
A node with no left child and no right child
Root-to-leaf path
The chain of nodes from the root down to any leaf
Remaining target
targetSum minus the values already consumed on the current path
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Enumerate every full path then sum

Correct but wastefully builds and stores whole paths when a boolean check suffices.

Collect each root-to-leaf path into a list, sum it, and compare.

Time O(n)Space O(n)
Best choiceSubtract-while-descending DFS

Constant extra work per node and short-circuits as soon as a match is found.

Pass the remaining target down the recursion; check it only at leaves.

Time O(n)Space O(h)
The rule we keep true

Invariant

When the recursion reaches a node, `remaining` equals the original targetSum minus the sum of all strict ancestors of that node.

Why this is correct

Reasoning

By construction, at a leaf `remaining` is the target minus the sum of every ancestor, so `remaining == leaf.val` holds exactly when the whole root-to-leaf sum equals targetSum. OR-combining the children reports true if any such leaf exists.

The algorithm in three movesSay these aloud before coding
1Return False on an empty node so a null child never counts as a path

at 5: need 22-5=17

2At a leaf, return whether the leaf value equals the remaining target

at 4: need 17-4=13

3Otherwise recurse into left and right with target reduced by the current value

at 11: need 13-11=2

4Combine children with OR — one qualifying path is enough

leaf 2: 2==2 -> true

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
50
41
112
23
1 · Readnode 5, target 22
2 · AskIs 5 a leaf?
3 · Update stateremaining becomes 17
4 · ResultRecurse left into 4 and right into 8
Key takeaway

The highlighted chain 5->4->11->2 is the root-to-leaf path whose values sum to 22.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Empty guard

    A null child is not a leaf and forms no path, so it can never satisfy the target.

  2. 2
    Lines 5-6Leaf test

    Only at a genuine leaf do we compare, ensuring the path ended at the bottom.

  3. 3
    Lines 7-8Recurse with reduced target

    Subtracting now lets the leaf test stay a simple equality, and OR stops early on success.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Empty tree returns false regardless of targetSum
  • Single-node tree where the root value equals targetSum returns true
  • Negative node values and negative targets must still work since we only subtract
  • A path that reaches the target at an internal node but not a leaf must NOT count
!

Common beginner mistakes

  • Treating a node with one child as a leaf — you must reach a node with no children
  • Returning true when `remaining` hits 0 at an internal node instead of at a leaf
  • Forgetting the empty-tree base case and crashing on a null root
Check your understanding

Why can't we simply return true whenever the accumulated sum equals targetSum at any node?

More in Trees and Binary Search Trees

#104Maximum Depth of Binary TreePost-order height aggregation#543Diameter of Binary TreePost-order height with a running best#102Binary Tree Level Order TraversalLevel-by-level BFS#98Validate Binary Search TreeRange-bounded validation#236Lowest Common Ancestor of a Binary TreeBottom-up LCA search#105Construct Binary Tree from Preorder and InorderPreorder root + inorder split