← DSA Atlas
Dedicated problem page · #129

Sum Root to Leaf Numbers

MediumTrees and Binary Search TreesRoot-to-leaf digit accumulationDFS carrying a running number
Solve on LeetCode ↗
129
MediumTrees and Binary Search TreesDFS carrying a running numberRoot-to-leaf digit accumulation

Sum Root to Leaf Numbers

Given the root of a binary tree where every node holds a single digit 0-9, each root-to-leaf path spells a number by reading digits from root to leaf. Return the total sum of all the numbers spelled by the root-to-leaf paths.

Open official problem prompt ↗
In plain English

Add up every number formed by reading digits along a root-to-leaf path.

Picture it like this

Like reading an odometer as you drive down each branch: each turn deeper shifts the current reading left by one place and drops in the next digit; you record the reading only when you reach the end of a road.

Example
Input
root = [1,2,3]
Output
25
Why
Path 1->2 spells 12 and path 1->3 spells 13; 12 + 13 = 25.
Constraints
The number of nodes is in the range [1, 1000]0 <= Node.val <= 9The depth of the tree will not exceed 10
Pattern lesson

See the pattern, then code

Root-to-leaf digit accumulation
Recognition clue

Each path builds a base-10 number and you need the sum over all paths — that means carry a running value that shifts left by one digit at every step down.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. Descending one level appends a digit, which is exactly `cur = cur * 10 + node.val`; the number is complete only at a leaf, so sum leaf values across all paths.

New words, made simpleKnow these before the algorithm
Base-10 shift
Multiplying by 10 to open a new units place for the next digit
Running number
The partial number formed by the ancestors of the current node
Leaf value
The completed path number, returned upward
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Collect path strings then convert

Correct but builds strings and stores full paths unnecessarily.

Gather each path as a string of digits, convert to int, and sum.

Time O(n)Space O(n)
Best choiceCarry an integer down the DFS

No string work; only stack depth is used.

Thread the running number through recursion, returning it at leaves.

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

Invariant

When dfs reaches a node, `cur` (before that node's own update) equals the number spelled by the node's ancestors from the root.

Why this is correct

Reasoning

Multiplying by 10 and adding the digit reproduces positional notation, so at a leaf `cur` is exactly the path's number. Summing the two child returns, with empty children contributing 0, adds each path's number exactly once.

The algorithm in three movesSay these aloud before coding
1Carry a running number cur starting at 0

root 1: cur=1

2At each node, update cur = cur * 10 + node.val

leaf 2: cur=12 -> return 12

3At a leaf, return cur as that path's number

leaf 3: cur=13 -> return 13

4Sum the results of the left and right recursions

total = 25

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
32
1 · Readnode 1, cur 0
2 · AskIs 1 a leaf?
3 · Update statecur = 0*10+1 = 1
4 · ResultRecurse left and right with cur=1
Key takeaway

Root 1 with leaves 2 and 3 forms the numbers 12 and 13.

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 4-5Null contributes zero

    A missing child adds nothing to the sum, keeping the recursion clean.

  2. 2
    Lines 6Shift and add digit

    This single line builds the positional number as we descend.

  3. 3
    Lines 7-9Leaf returns, else recurse

    Only leaves finalize a number; internal nodes pass the running value down and sum the branches.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single node returns that node's value
  • All digits zero still sum correctly (to zero)
  • A skewed tree (one long path) yields a single multi-digit number
  • Node values are single digits, so no digit ever exceeds 9
!

Common beginner mistakes

  • Summing internal-node values instead of only leaf-completed numbers
  • Resetting cur to 0 at each node instead of threading the ancestor value
  • Concatenating strings and forgetting to convert to int before summing
Check your understanding

Why do we finalize the number only at a leaf and not at every 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