DSA AnimatorDSA animations
Path Sum LC #112 Easy DFS · Remainder Tracking
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.

Example 1
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: Path 5→4→11→2 sums to 22.
Example 2
Input: root = [1,2,3], targetSum = 5
Output: false
Constraints: 0 ≤ nodes ≤ 5000  |  −1000 ≤ Node.val, targetSum ≤ 1000
Try Examples
Custom:
Approach
DFS: subtract node.val from remainder at every step
Pass rem = target − node.val downward. At a leaf, check rem == 0. Use left || right to short-circuit once a valid path is found.
Binary Tree
Current Path
No path yet…
Remainder Tracker
Remaining
—
Waiting for first node…
State Variables
node.val
—
rem
—
isLeaf?
—
found
—
Step Logic
Load an example to begin.
Recursion Stack
Stack is empty
Algorithm Steps
Time
O(n)
Space
O(h)
Why it Works

Passing rem = target − node.val converts the path-sum check into a single equality at the leaf: rem == 0. The || operator short-circuits — once any valid path is found the recursion unwinds immediately without exploring further nodes.

How to solve Path Sum

LeetCode 112 · Easy · Tree · Pattern: DFS with Remaining Target

Why the obvious approach is slow

You could list every root to leaf path and sum each one. But we can carry the remaining amount down the tree instead, and never store a path.

The key idea

Subtract the node value from the target as you go down. At a leaf, check whether the remaining amount is exactly 0. If either subtree returns true, the answer is true. The check must happen only at leaves, because a path has to end at a leaf.

Remember

Pass the remaining target down, and check it only at leaves. The or operator stops the search as soon as one path works.

Run the animation above on your own input, or watch the 1:43 video explanation of Path Sum with a dry run and Java code.

More Tree problems