Sum Root to Leaf Numbers — Solution in Python, Java & C++
Sum Root to Leaf Numbers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Sum Root to Leaf Numbers is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary tree in which every node holds a single digit from 0 to 9. Each root-to-leaf path spells a number: the digits read from the root down to the leaf (a node with no children). For example the path 1 → 2 → 3 spells 123.
Return the sum of the numbers spelled by all root-to-leaf paths. The answer fits in a 32-bit signed integer.
Example 1
Input: root = [1,2,3]
Output: 25
Explanation: The paths spell 12 and 13, and 12 + 13 = 25.
Example 2
Input: root = [4,9,0,5,1]
Output: 1026
Explanation: The paths spell 495, 491 and 40, and 495 + 491 + 40 = 1026.
Example 3
Input: root = [0,1]
Output: 1
Explanation: The only path spells 01, which is the number 1.
Constraints
1 <= number of nodes <= 10000 <= Node.val <= 9the depth of the tree does not exceed 10the answer fits in a 32-bit signed integer
Hints for Sum Root to Leaf Numbers
Hint 1
Appending a digit
dto a numberxgives10 * x + d.Hint 2
Walk from the root downwards carrying the number spelled so far.
Hint 3
At a leaf the carried number is complete — add it to the total. An inner node only passes its number on to its children.
How to solve Sum Root to Leaf Numbers
Carry the number spelled so far down a depth-first walk; at each node it becomes 10 * carried + digit, and each leaf contributes the number that reaches it.
Approach
- Visit the root with a carried value of 0.
- At a node, set
cur = 10 * carried + node.val. - If the node is a leaf, return
cur. - Otherwise return the sum of the results for its existing children, each visited with
cur.
Why it works
The value reaching a node is exactly the number spelled by the path from the root to it, by induction: the root gets its own digit, and a child gets its parent's number with its digit appended. Every leaf is reached once, so every root-to-leaf number is added once.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion
Pitfalls
- A node with one child is not a leaf — do not count its partial number.
- Leading zeros are fine: the path
0 → 1spells 1.
Reference solution
Python
from typing import Optional
def sumNumbers(root: Optional[TreeNode]) -> int:
def walk(node, cur):
cur = cur * 10 + node.val
if node.left is None and node.right is None:
return cur
total = 0
if node.left:
total += walk(node.left, cur)
if node.right:
total += walk(node.right, cur)
return total
return walk(root, 0) if root else 0Java
public static int sumNumbers(TreeNode root) {
return root == null ? 0 : digitWalk(root, 0);
}
static int digitWalk(TreeNode node, int cur) {
cur = cur * 10 + node.val;
if (node.left == null && node.right == null) return cur;
int total = 0;
if (node.left != null) total += digitWalk(node.left, cur);
if (node.right != null) total += digitWalk(node.right, cur);
return total;
}C++
int digitWalk(TreeNode* node, int cur);
int sumNumbers(TreeNode* root) {
return root ? digitWalk(root, 0) : 0;
}
int digitWalk(TreeNode* node, int cur) {
cur = cur * 10 + node->val;
if (!node->left && !node->right) return cur;
int total = 0;
if (node->left) total += digitWalk(node->left, cur);
if (node->right) total += digitWalk(node->right, cur);
return total;
}JavaScript
var sumNumbers = function(root) {
return root === null ? 0 : digitWalk(root, 0);
};
var digitWalk = function(node, cur) {
cur = cur * 10 + node.val;
if (node.left === null && node.right === null) return cur;
var total = 0;
if (node.left !== null) total += digitWalk(node.left, cur);
if (node.right !== null) total += digitWalk(node.right, cur);
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals