Sum Root to Leaf Numbers
Sum Root to Leaf Numbers is a medium trees & bst problem solved with the recursion pattern.
The best approach, optimal (dfs carrying the number), runs in O(n) time and O(h) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (collect path strings) up.
Problem
Every node of a binary tree holds a single digit from 0 to 9. Reading the digits along a path from the root down to a leaf spells out a number; for example, the path 5 -> 0 -> 2 stands for 502.
Return the sum of the numbers spelled by all root-to-leaf paths. A leaf is a node with no children.
Examples
Example 1
- Input
root = [2, 7, 3, null, 4]- Output
297- Why
- The two root-to-leaf paths spell 274 and 23, and 274 + 23 = 297.
Example 2
- Input
root = [6, 0, null, 1, 8]- Output
1209- Why
- Both leaves hang under the 0, giving 601 and 608. The 0 in the middle still counts as a digit.
Example 3
- Input
root = [9]- Output
9- Why
- The root is also a leaf, so the only number is 9.
Constraints
- The tree has between
1and1000nodes. 0 <= Node.val <= 9- The depth of the tree is at most
10. - The answer fits in a 32-bit signed integer.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (collect path strings) | O(n · h) | O(n · h) |
| Optimal (DFS carrying the number) | O(n) | O(h) |
1Brute force (collect path strings)
O(n · h)Building a string copy at each node costs up to h characters; parsing the leaves' strings costs O(h) each.O(n · h)Up to n / 2 leaf strings of length up to h, plus the recursion stack.Walk every root-to-leaf path while building a string of its digits. At each leaf, save the string. Afterwards, parse each string as a number and add them up.
- DFS from the root, appending the current digit to a path string.
- At a leaf, add the finished string to a list.
- Parse every string in the list and sum the values.
class Solution {
public int sumNumbers(TreeNode root) {
List<String> paths = new ArrayList<>();
collect(root, "", paths);
long total = 0;
for (String p : paths) total += Long.parseLong(p);
return (int) total;
}
private void collect(TreeNode node, String path, List<String> paths) {
if (node == null) return;
String next = path + node.val;
if (node.left == null && node.right == null) {
paths.add(next);
return;
}
collect(node.left, next, paths);
collect(node.right, next, paths);
}
}class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
paths = []
self.collect(root, "", paths)
return sum(int(p) for p in paths)
def collect(self, node: Optional[TreeNode], path: str, paths: List[str]) -> None:
if node is None:
return
nxt = path + str(node.val)
if node.left is None and node.right is None:
paths.append(nxt)
return
self.collect(node.left, nxt, paths)
self.collect(node.right, nxt, paths)class Solution {
public:
int sumNumbers(TreeNode* root) {
vector<string> paths;
collect(root, "", paths);
long long total = 0;
for (auto& p : paths) total += stoll(p);
return (int) total;
}
private:
void collect(TreeNode* node, string path, vector<string>& paths) {
if (node == nullptr) return;
string next = path + to_string(node->val);
if (node->left == nullptr && node->right == nullptr) {
paths.push_back(next);
return;
}
collect(node->left, next, paths);
collect(node->right, next, paths);
}
};function sumNumbers(root) {
const paths = [];
collect(root, "", paths);
let total = 0;
for (const p of paths) total += parseInt(p, 10);
return total;
}
function collect(node, path, paths) {
if (node === null) return;
const next = path + node.val;
if (node.left === null && node.right === null) {
paths.push(next);
return;
}
collect(node.left, next, paths);
collect(node.right, next, paths);
}2Optimal (DFS carrying the number)
O(n)Every node is visited once with O(1) work.O(h)The recursion stack is as deep as the tree, at most 10 here.Carry the number built so far down the recursion instead of a string. Appending a digit is cur * 10 + val. A leaf returns its finished number; any other node returns the sum of what its children return. A missing child contributes 0.
- dfs(node, cur): if node is null, return 0.
- cur = cur * 10 + node.val.
- If node is a leaf, return cur.
- Otherwise return dfs(node.left, cur) + dfs(node.right, cur).
- The answer is dfs(root, 0).
class Solution {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
private int dfs(TreeNode node, int cur) {
if (node == null) return 0;
cur = cur * 10 + node.val;
if (node.left == null && node.right == null) return cur;
return dfs(node.left, cur) + dfs(node.right, cur);
}
}class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
return self.dfs(root, 0)
def dfs(self, node: Optional[TreeNode], cur: int) -> int:
if node is None:
return 0
cur = cur * 10 + node.val
if node.left is None and node.right is None:
return cur
return self.dfs(node.left, cur) + self.dfs(node.right, cur)class Solution {
public:
int sumNumbers(TreeNode* root) {
return dfs(root, 0);
}
private:
int dfs(TreeNode* node, int cur) {
if (node == nullptr) return 0;
cur = cur * 10 + node->val;
if (node->left == nullptr && node->right == nullptr) return cur;
return dfs(node->left, cur) + dfs(node->right, cur);
}
};function sumNumbers(root) {
return dfs(root, 0);
}
function dfs(node, cur) {
if (node === null) return 0;
cur = cur * 10 + node.val;
if (node.left === null && node.right === null) return cur;
return dfs(node.left, cur) + dfs(node.right, cur);
}Edge cases to test
- A single node: the answer is its own digit
- Zeros along a path, including a 0 at the root (leading zero)
- A node with only one child is not a leaf; only the child's side forms a number
- A skewed tree that is one long path
Hints
Hint 1
Each path builds its number one digit at a time. If the number so far is cur and the next digit is d, what is the new number?
Hint 2
Pass cur * 10 + node.val down the recursion and add it to the total only when you reach a leaf.
FAQ
What is the best time complexity for Sum Root to Leaf Numbers?
Optimal (DFS carrying the number) runs in O(n) time and O(h) extra space. Every node is visited once with O(1) work.
Which pattern does Sum Root to Leaf Numbers use?
It is a trees & bst problem that uses the recursion pattern. Other problems with the same pattern: Binary Tree Inorder Traversal (Recursive), Binary Tree Preorder Traversal (Recursive), Binary Tree Postorder Traversal (Recursive).
Is there a brute force solution for Sum Root to Leaf Numbers?
Yes. Brute force (collect path strings) takes O(n · h) time and O(n · h) space. Walk every root-to-leaf path while building a string of its digits.
Which edge cases should I test for Sum Root to Leaf Numbers?
A single node: the answer is its own digit; Zeros along a path, including a 0 at the root (leading zero); A node with only one child is not a leaf; only the child's side forms a number; A skewed tree that is one long path.