DSA AnimatorDSA animations
Sum Root to Leaf Numbers LC #129 Medium DFS · Digit Accumulation
Problem

You are given the root of a binary tree containing digits from 0–9. Each root-to-leaf path represents a number (e.g., 1→2→3 = 123). Return the total sum of all root-to-leaf numbers.

Example 1
Input: root = [1,2,3]
Output: 25
Explanation: Paths: 1→2=12, 1→3=13. Sum=12+13=25.
Example 2
Input: root = [4,9,0,5,1]
Output: 1026
Explanation: Paths: 4→9→5=495, 4→9→1=491, 4→0=40. Sum=495+491+40=1026.
Constraints: 1 ≤ nodes ≤ 1000  |  0 ≤ Node.val ≤ 9  |  tree depth ≤ 10
Try Examples
Custom:
Approach
DFS: curr = curr × 10 + node.val at every step
Accumulate the number digit-by-digit as we go deeper. At a leaf, curr is one complete number — add it to the total. Internal nodes return dfs(left, curr) + dfs(right, curr).
Binary Tree
Number Builder
Waiting for first node…
Current Path
—
Leaf Numbers
No leaf reached yet…
State Variables
node.val
—
curr
0
isLeaf?
—
leafNums
[]
Step Logic
Load an example to begin.
Recursion Stack
Stack is empty
Algorithm Steps
Time
O(n)
Space
O(h)
Why it Works

Multiplying by 10 and adding the next digit is exactly how decimal numbers are formed — curr = curr×10 + digit. At each leaf we have the complete root-to-leaf number. Summing the left and right DFS calls automatically accumulates all leaf contributions. No extra path storage needed.

How to solve Sum Root to Leaf Numbers

LeetCode 129 · Medium · Tree · Pattern: DFS Carry Value

Why the obvious approach is slow

You could build each path as a string and convert it at the leaf. Carrying the number as an integer is simpler and faster.

The key idea

Carry the number formed so far, starting from 0. At each node, multiply it by 10 and add the node digit. At a leaf, that is one complete number, so return it. At other nodes, return the sum of the left and right results.

Remember

Times 10 plus the digit builds the number on the way down. Leaves return numbers, and parents add them up.

Run the animation above on your own input, or watch the 1:45 video explanation of Sum Root to Leaf Numbers with a dry run and Java code.

More Tree problems