Sum Root to Leaf Numbers
Read each root-to-leaf path of a digit tree as a number and add them all up. A depth-first search that carries a running value down the tree. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given the root of a binary tree in which every node holds a single digit from 0 to 9.
Each path from the root down to a leaf (a node with no children) spells out a number: read the digits from top to bottom. For example, the path 4 → 0 → 7 is the number 407.
Return the sum of the numbers for every root-to-leaf path. The tree is given in level order, with null marking a missing child.
Example 1
- Input
- root = [3, 7, 2, 1, null, 8, 6]
- Output
- 1025
The paths are 3 → 7 → 1, 3 → 2 → 8 and 3 → 2 → 6, so 371 + 328 + 326 = 1025.
Example 2
- Input
- root = [0, 1, 2]
- Output
- 3
The paths read 01 and 02, which are the numbers 1 and 2.
Example 3
- Input
- root = [2, 0, 0, null, 3, null, 4]
- Output
- 407
The two paths are 203 and 204. Each 0 node has only a right child, so it is not a leaf.
Constraints
- The number of nodes is in the range [1, 1023].
- 0 ≤ Node.val ≤ 9
- The depth of the tree is at most 10.
Practice
Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Sum Root to Leaf Numbers in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Sum Root to Leaf Numbers
Pattern: DFS with a running prefix value
Appending a digit d to a number n gives n * 10 + d. So as you walk down the tree, you never need the path as a string: carry the number built so far, and at each node update it to current * 10 + node.val.
When you reach a leaf, that running value is one complete number, so add it to the total. Internal nodes contribute nothing on their own; they only shape the prefixes of the leaves below them.
Approach 1: Collect paths as strings
Run a DFS that builds each root-to-leaf path as a string or list of digits, then convert each one to an integer and sum. Correct, but copies a path of length h at every leaf.
Time O(n · h) · Space O(n · h) for the stored paths
Approach 2: DFS carrying the number so far
Use a stack of (node, value) pairs, starting with (root, 0).
- Pop a pair and compute
value = value * 10 + node.val. - If the node is a leaf, add
valueto the total. - Otherwise push each existing child with the new
value.
Recursion works the same way; the explicit stack just avoids deep call stacks on skewed trees.
Time O(n) · Space O(h) recursive, O(n) worst case for the stack
| Approach | Time | Space |
|---|---|---|
| Collect paths as strings | O(n · h) | O(n · h) for the stored paths |
| DFS carrying the number so far | O(n) | O(h) recursive, O(n) worst case for the stack |
Solution code
Try the practice editor first. Both solutions pass every test above.
Sum Root to Leaf Numbers solution in Python
def sum_numbers(root: Optional[TreeNode]) -> int:
total = 0
stack = [(root, 0)]
while stack:
node, value = stack.pop()
value = value * 10 + node.val
if not node.left and not node.right:
total += value
continue
for child in (node.left, node.right):
if child:
stack.append((child, value))
return totalSum Root to Leaf Numbers solution in JavaScript
function sumNumbers(root) {
let total = 0;
const stack = [[root, 0]];
while (stack.length) {
const [node, prefix] = stack.pop();
const value = prefix * 10 + node.val;
if (!node.left && !node.right) {
total += value;
continue;
}
if (node.left) stack.push([node.left, value]);
if (node.right) stack.push([node.right, value]);
}
return total;
}Common mistakes
- Adding the value at a node with one child. A leaf must have **no** children.
- Treating a missing child as a leaf, which double-counts paths when a node has only one child.
- Dropping leading zeros by building strings and stripping them, or the reverse: forgetting that "01" is just 1.
- Using a 32-bit integer when the depth allows 10 digits. 9,999,999,999 does not fit.
What interviewers look for
Mention the value * 10 + digit update first; it is the whole trick and shows you are not building strings. Then be explicit about the leaf check (both children missing), since that is where most bugs hide.
If you write it recursively, point out that the recursion depth is the tree height and offer the iterative version if the tree could be very deep.
Follow-up questions
Can you do it with O(1) extra space?
Yes, with a Morris traversal. It threads temporary right pointers from each node's in-order predecessor back to the node, so you can walk the tree without a stack. You track the current number and undo the digits of the threaded segment when you climb back, which takes care but uses constant space.
What if node values could be any non-negative integer, not just digits?
Concatenation then shifts by the number of digits in the value: `value * 10^(digits of node.val) + node.val`. Everything else stays the same.
What if the answer could be huge and you had to return it modulo 10⁹ + 7?
Take the running value modulo 10⁹ + 7 at every step. Both multiplication by 10 and addition are compatible with the modulus, so the final sum is correct.
Companies that ask Sum Root to Leaf Numbers
Sum Root to Leaf Numbers is tagged by 89 companies in our interview dataset. The score shows how often it comes up at each company.
- Applied Materials100%
- Telus100%
- Hackerrank100%
- Vtex98%
- Genesys98%
- Greenlight98%
- Abbott97%
- Chegg90%
- Grainger88%
- Gigamon87%
- Arm84%
- Coffee Meets Bagel84%
- Toyota Usa83%
- Fujitsu83%
- Costco Wholesale82%
- Check2482%
- Extrahop81%
- Root Insurance80%
- Meta78.4%
- Nisum77%
- Offerup75%
- Boeing72%
- Pathai72%
- Paylocity72%
and 65 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required