← Back to DSA Animator
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.