Log inSign up
mediumleetcodeNot Started

Sum Root to Leaf Numbers

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number: - For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123. Return the total sum of all root-to-leaf numbers. A leaf is a node with no children.

Example 1 · Example 1: Two Paths:

Input: root = [1, 2, 3] Tree: 1 / \ 2 3
Output: 25
Explanation: Path 1->2 forms 12. Path 1->3 forms 13. Total sum = 12 + 13 = 25.

Example 2 · Example 2: 3-Level Tree:

Input: root = [4, 9, 0, 5, 1] Tree: 4 / \ 9 0 / \ 5 1
Output: 1026
Explanation: 4->9->5 is 495. 4->9->1 is 491. 4->0 is 40. Total = 495 + 491 + 40 = 1026.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • 0 <= Node.val <= 9
  • The depth of the tree will not exceed 10.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Accumulate base-10 numbers down tree branches.
  • Identify leaf node termination.
  • Combine subtree sums with recursion.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Root-to-leaf path forms a base-10 number.
  • Digits 0 to 9 in nodes.
  • Sum of path-formed integers.

Algorithmic Decision Tree:

  • curr = curr * 10 + node.val.
  • if leaf -> return curr.
  • return dfs(left, curr) + dfs(right, curr).

Connected Patterns:

Path SumBinary Tree PathsSmallest String Starting From Leaf

1. String Path Building + Integer Conversion

Intuition

Recursively build string path. When reaching a leaf, convert string to integer and add to total sum.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Helper dfs(node, strPath, total).
  2. Step 2: If leaf, total += stoi(strPath + to_string(node.val)).
  3. Step 3: Recurse left and right with strPath + to_string(node.val).
  4. Step 4: Return total.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 int total = 0;
9 void dfs(TreeNode* node, string s) {
10 if (!node) return;
11 s += to_string(node->val);
12 if (!node->left && !node->right) {
13 total += stoi(s);
14 return;
15 }
16 dfs(node->left, s);
17 dfs(node->right, s);
18 }
19public:
20 int sumNumbers(TreeNode* root) {
21 dfs(root, "");
22 return total;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n * h) — String copying takes O(h) per node.
  • Space complexity: O(h) — String path takes O(h) memory.

2. Iterative BFS with Queue of (Node, CurrentNum)

Intuition

Push (root, root.val) to queue. Pop (node, val). If leaf, add val to total. Else push children with val * 10 + child.val.

When to apply: Iterative queue-based solution.

Algorithm

  1. Step 1: If root == null return 0.
  2. Step 2: Queue stores pairs (node, num). Push (root, root.val).
  3. Step 3: Pop (node, val). If leaf, total += val.
  4. Step 4: Push children with val * 10 + child.val.
  5. Step 5: Return total.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int sumNumbers(TreeNode* root) {
10 if (!root) return 0;
11 int total = 0;
12 queue<pair<TreeNode*, int>> q;
13 q.push({root, root->val});
14 while (!q.empty()) {
15 auto [node, num] = q.front(); q.pop();
16 if (!node->left && !node->right) {
17 total += num;
18 }
19 if (node->left) q.push({node->left, num * 10 + node->left->val});
20 if (node->right) q.push({node->right, num * 10 + node->right->val});
21 }
22 return total;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n) — Every node visited once.
  • Space complexity: O(w) — Queue holds level width w.

3. Clean Recursive DFS with Base-10 Arithmetic

Intuition

Base case: if node is null return 0. Update curr = curr * 10 + node.val. If leaf, return curr. Return dfs(left, curr) + dfs(right, curr).

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: Helper dfs(node, curr): if null return 0.
  2. Step 2: curr = curr * 10 + node.val.
  3. Step 3: If leaf (left == null && right == null) return curr.
  4. Step 4: Return dfs(node.left, curr) + dfs(node.right, curr).

Decimal Shift Trace for root = [1, 2, 3]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Start at root 1
Visual state
Values and pointers at this exact step
tree
Root
1 (curr: 1)
L
2
R
3

Node order shown; add connections to display explicit tree edges.

curr: 1: 1
Check / comparison
Root digit: 1
Decision / next transition
Pass curr = 1 to children.
Why this step matters

Step 1: Start at root 1. curr = 1. Branch to left child 2 and right child 3.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 int dfs(TreeNode* node, int curr) {
9 if (!node) return 0;
10 curr = curr * 10 + node->val;
11 if (!node->left && !node->right) return curr;
12 return dfs(node->left, curr) + dfs(node->right, curr);
13 }
14public:
15 int sumNumbers(TreeNode* root) {
16 return dfs(root, 0);
17 }
18};
19
20int main() {
21 // Sample driver execution
22 cout << "Execution completed successfully." << endl;
23 return 0;
24}
25

Time & Space Complexity

  • Time complexity: O(n) — Processes each node in O(1) time.
  • Space complexity: O(h) — Recursion call stack takes O(h) space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.String ConversionO(n * h)O(h)Concatenate string digits and parse.String concatenation.
2.Iterative BFS QueueO(n)O(w)Queue holds pair (node, num).Queue.
3.Clean Recursive DFSOptimalO(n)O(h)Arithmetic curr * 10 + val; return left + right.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single node tree: root = [1] -> returns 1.
  • Single node with 0: root = [0] -> returns 0.
  • Skewed tree: returns single multi-digit number.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Contrast string accumulation (e.g. converting strings to ints) with arithmetic curr * 10 + node.val.
  2. Explain why passing curr by value cleanly branches without side-effects.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is curr = curr * 10 + node.val preferred over string concatenation s += node.val?

Back to DSA Sheet