152. Sum Root to Leaf Numbers
🔗 LeetCode Problem: 129. Sum Root to Leaf Numbers
📊 Difficulty: Medium
🏷️ Topics: Binary Trees, DFS, Path Sum, Number Formation, Recursion
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. Test cases are generated so that the answer will fit in a 32-bit integer.
A leaf node is a node with no children.
Example 1:
Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.
Example 2:
Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 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
🌳 Visual Understanding - Building Numbers from Paths
What is a Root-to-Leaf Number?
Tree:
1
/ \
2 3
Root-to-leaf paths:
1. [1, 2] → represents number: 1×10 + 2 = 12
2. [1, 3] → represents number: 1×10 + 3 = 13
Total sum: 12 + 13 = 25
How Numbers are Formed:
Path: 1 → 2 → 3
Step-by-step number formation:
Start: 0
Node 1: 0×10 + 1 = 1
Node 2: 1×10 + 2 = 12
Node 3: 12×10 + 3 = 123
Final number: 123
Formula: currentNumber = previousNumber × 10 + nodeValue
Example 2 - Visual Breakdown:
Tree:
4
/ \
9 0
/ \
5 1
Root-to-leaf numbers:
Path 1: 4 → 9 → 5
At 4: 0×10 + 4 = 4
At 9: 4×10 + 9 = 49
At 5: 49×10 + 5 = 495 ✓
Path 2: 4 → 9 → 1
At 4: 0×10 + 4 = 4
At 9: 4×10 + 9 = 49
At 1: 49×10 + 1 = 491 ✓
Path 3: 4 → 0
At 4: 0×10 + 4 = 4
At 0: 4×10 + 0 = 40 ✓
Total: 495 + 491 + 40 = 1026
Key Observations:
1. Each path forms ONE number
- Not individual digits
- Concatenated as if string, but calculated as int
2. Must reach LEAF to complete number
- Can't stop at internal nodes
- Only leaves contribute to sum
3. Number builds incrementally
- Previous × 10 + current
- Carries down through recursion
Similar to Path Sum II, but BUILD numbers! 🎯
🧠 The AHA Moment - Two Approaches!
Approach 1: Pass Current Number Down (Accumulator)
Pass the current number as parameter:
dfs(node, currentNumber):
At each node:
newNumber = currentNumber × 10 + node.val
At leaf:
Return newNumber
At internal node:
Return sum from left + sum from right
Numbers built top-down! 📉
Approach 2: Build Number with Path (Like Path Sum II)
Maintain path list (like Problem 151):
dfs(node, path):
Add node to path
At leaf:
Convert path to number
Add to result
Backtrack
Similar to Path Sum II! 🔄
Visual Comparison:
APPROACH 1 (Accumulator):
4 (curr=4)
/ \
9 0 (curr=40)
/ \
5 1
(495) (491)
Return: 495 + 491 + 40 = 1026
APPROACH 2 (Path):
4 [4]
/ \
9 0 [4,0]
/ \
5 1
[4,9,5] [4,9,1]
Convert to numbers, sum
Both work! Approach 1 cleaner! ✓
🧠 Recursive Thinking - Building the Solution
Base Case:
When at null?
→ Return 0 (contributes nothing)
When at leaf?
→ Return the complete number
if (node == null) return 0;
if (node.left == null && node.right == null) {
return currentNumber × 10 + node.val;
}
Recursive Case (Accumulator Approach):
For any node:
STEP 1: Build current number
currentNumber = previousNumber × 10 + node.val
STEP 2: If leaf, return number
if (leaf):
return currentNumber
STEP 3: Get sums from children
leftSum = dfs(node.left, currentNumber)
rightSum = dfs(node.right, currentNumber)
STEP 4: Return total
return leftSum + rightSum
What Each Node Returns:
Leaf nodes:
Return: Complete number formed by path
Internal nodes:
Return: Sum of all numbers in subtree
Root:
Return: Sum of ALL root-to-leaf numbers
Example:
Node 5 (leaf): returns 495
Node 1 (leaf): returns 491
Node 9: returns 495 + 491 = 986
Node 0 (leaf): returns 40
Root 4: returns 986 + 40 = 1026
🎯 Solution 1: DFS with Accumulator (Optimal)
Implementation:
class Solution {
public int sumNumbers(TreeNode root) {
// Start with current number = 0
return dfs(root, 0);
}
private int dfs(TreeNode node, int currentNumber) {
// Base case: null node contributes 0
if (node == null) {
return 0;
}
// STEP 1: Build current number
// Add current digit to the number we're building
// Formula: previousNumber × 10 + currentDigit
currentNumber = currentNumber * 10 + node.val;
// STEP 2: Check if leaf
// If leaf, this number is complete!
if (node.left == null && node.right == null) {
return currentNumber;
}
// STEP 3: Recurse on children
// Get sum of all numbers in left subtree
int leftSum = dfs(node.left, currentNumber);
// Get sum of all numbers in right subtree
int rightSum = dfs(node.right, currentNumber);
// STEP 4: Return total sum from both subtrees
return leftSum + rightSum;
}
}
Why This Works:
currentNumber parameter carries the number built so far:
At root 4: currentNumber = 4
Pass 4 to children
At node 9: currentNumber = 4×10 + 9 = 49
Pass 49 to children
At node 5: currentNumber = 49×10 + 5 = 495
Leaf! Return 495
Number builds naturally as we descend! 🎯
🎯 Solution 2: DFS with Helper (Cleaner Leaf Check)
Implementation:
class Solution {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
private int dfs(TreeNode node, int currentNumber) {
if (node == null) {
return 0;
}
// Build current number
currentNumber = currentNumber * 10 + node.val;
// If leaf, return this number
if (node.left == null && node.right == null) {
return currentNumber;
}
// Otherwise, recurse and sum
return dfs(node.left, currentNumber) + dfs(node.right, currentNumber);
}
}
Simplified Logic:
Combines the recursive calls in return statement:
return left + right
Instead of:
leftSum = ...
rightSum = ...
return leftSum + rightSum
More concise! ✨
🎯 Solution 3: With Global Variable (Alternative)
Implementation:
class Solution {
private int totalSum;
public int sumNumbers(TreeNode root) {
totalSum = 0;
dfs(root, 0);
return totalSum;
}
private void dfs(TreeNode node, int currentNumber) {
if (node == null) {
return;
}
// Build current number
currentNumber = currentNumber * 10 + node.val;
// If leaf, add to total
if (node.left == null && node.right == null) {
totalSum += currentNumber;
return;
}
// Recurse on children
dfs(node.left, currentNumber);
dfs(node.right, currentNumber);
}
}
Global Variable Approach:
Instead of returning sum:
- Accumulate in global variable
- Void function (no return)
- Add to totalSum at leaves
Similar to Problem 147 (Max Path Sum)!
But less elegant here - prefer return approach ✓
🔍 Detailed Dry Run - Complete Recursion
Tree:
1
/ \
2 3
Complete Call Stack:
═══════════════════════════════════════════════════
CALL STACK - NUMBER FORMATION
═══════════════════════════════════════════════════
Level 0: dfs(1, 0)
│
├─ currentNumber = 0 × 10 + 1 = 1
├─ Not leaf (has children)
│
├─ LEFT: dfs(2, 1) ────────────────────────────────┐
│ │
│ Level 1: dfs(2, 1) │
│ │ │
│ ├─ currentNumber = 1 × 10 + 2 = 12 │
│ ├─ IS LEAF! │
│ ├─ Both children null │
│ │ │
│ └─ return 12 │
│ │
├─ leftSum = 12 │
│ │
├─ RIGHT: dfs(3, 1) ───────────────────────────────┐
│ │
│ Level 1: dfs(3, 1) │
│ │ │
│ ├─ currentNumber = 1 × 10 + 3 = 13 │
│ ├─ IS LEAF! │
│ ├─ Both children null │
│ │ │
│ └─ return 13 │
│ │
├─ rightSum = 13 │
│ │
└─ return leftSum + rightSum = 12 + 13 = 25 │
═══════════════════════════════════════════════════
FINAL: 25
═══════════════════════════════════════════════════
Number Formation at Each Step:
Node 1: curr = 0 × 10 + 1 = 1
Pass 1 to children
Node 2: curr = 1 × 10 + 2 = 12
Leaf! Return 12
Node 3: curr = 1 × 10 + 3 = 13
Leaf! Return 13
Root: 12 + 13 = 25
🔍 Complex Example Dry Run
Tree:
4
/ \
9 0
/ \
5 1
Complete Execution:
═══════════════════════════════════════════════════
CALL STACK - BUILDING NUMBERS
═══════════════════════════════════════════════════
Level 0: dfs(4, 0)
│
├─ currentNumber = 0 × 10 + 4 = 4
├─ Not leaf
│
├─ LEFT: dfs(9, 4) ────────────────────────────────┐
│ │
│ Level 1: dfs(9, 4) │
│ │ │
│ ├─ currentNumber = 4 × 10 + 9 = 49 │
│ ├─ Not leaf │
│ │ │
│ ├─ LEFT: dfs(5, 49) ──────────────────────┐ │
│ │ │ │
│ │ Level 2: dfs(5, 49) │ │
│ │ │ │ │
│ │ ├─ currentNumber = 49 × 10 + 5 = 495 │ │
│ │ ├─ IS LEAF! │ │
│ │ │ │ │
│ │ └─ return 495 │ │
│ │ │ │
│ ├─ leftSum = 495 │ │
│ │ │
│ ├─ RIGHT: dfs(1, 49) ─────────────────────┐ │
│ │ │ │
│ │ Level 2: dfs(1, 49) │ │
│ │ │ │ │
│ │ ├─ currentNumber = 49 × 10 + 1 = 491 │ │
│ │ ├─ IS LEAF! │ │
│ │ │ │ │
│ │ └─ return 491 │ │
│ │ │ │
│ ├─ rightSum = 491 │ │
│ │ │
│ └─ return 495 + 491 = 986 │
│ │
├─ leftSum = 986 │
│ │
├─ RIGHT: dfs(0, 4) ───────────────────────────────┐
│ │
│ Level 1: dfs(0, 4) │
│ │ │
│ ├─ currentNumber = 4 × 10 + 0 = 40 │
│ ├─ IS LEAF! │
│ │ │
│ └─ return 40 │
│ │
├─ rightSum = 40 │
│ │
└─ return 986 + 40 = 1026 │
═══════════════════════════════════════════════════
FINAL: 1026
═══════════════════════════════════════════════════
Numbers formed:
Path 4→9→5: 495 ✓
Path 4→9→1: 491 ✓
Path 4→0: 40 ✓
Total: 495 + 491 + 40 = 1026 ✓
Return Values at Each Node:
Node 5: returns 495 (leaf)
Node 1: returns 491 (leaf)
Node 9: returns 986 (495 + 491)
Node 0: returns 40 (leaf)
Node 4: returns 1026 (986 + 40)
📊 Complexity Analysis
Time Complexity: O(n)
Visit each node exactly once
O(1) work per node
- Arithmetic operation
- Add to result
Total: O(n)
Space Complexity: O(h)
Recursion stack: O(h)
Best case (balanced): O(log n)
Worst case (skewed): O(n)
No additional data structures needed!
Very space efficient ✓
⚠️ Common Mistakes
Mistake 1: Wrong Number Formation
// ❌ WRONG - Adding instead of building number
currentNumber = currentNumber + node.val; // WRONG!
// Example: Path [1, 2, 3]
// 1 + 2 = 3
// 3 + 3 = 6
// Should be 123, not 6! ✗
// ✓ CORRECT - Multiply by 10 and add
currentNumber = currentNumber * 10 + node.val; ✓
// Example: Path [1, 2, 3]
// 0 × 10 + 1 = 1
// 1 × 10 + 2 = 12
// 12 × 10 + 3 = 123 ✓
Mistake 2: Not Checking Both Children Null
// ❌ WRONG - Might count internal nodes
if (node.left == null || node.right == null) { // WRONG!
return currentNumber;
}
// Problem: Returns at nodes with one child!
// Tree: 1
// /
// 2
// Would return at node 1 (has only left) ✗
// Should only return at leaves (both null) ✓
// ✓ CORRECT - Both must be null
if (node.left == null && node.right == null) { ✓
return currentNumber;
}
Mistake 3: Modifying Parameter Before Using
// ❌ WRONG - Modifies before passing
private int dfs(TreeNode node, int currentNumber) {
if (node == null) return 0;
currentNumber = currentNumber * 10 + node.val; // Modified
// Problem: Pass modified value to null children!
return dfs(node.left, currentNumber) +
dfs(node.right, currentNumber);
}
// If node.left is null:
// dfs(null, 40) returns 0
// But we've already included node in number! ✗
// ✓ CORRECT - This is actually fine!
// The null check returns 0, so no issue
// But conceptually clearer to check leaf first
Mistake 4: Not Handling Single Node Tree
// ❌ WRONG - Assumes at least two nodes
if (node.left == null && node.right == null) {
return currentNumber; // Never reached if tree = [5]
}
// Actually this IS correct!
// Single node IS a leaf (both children null)
// Would return correctly ✓
// Common misconception: Need special case
// Not needed! Leaf check handles it ✓
Mistake 5: Building Number Wrong for 0
// Common question: What about leading zeros?
// Tree: 0
// / \
// 1 2
// Path [0, 1] should be 01 = 1 or 01?
// Answer: 1 (it's a number, not a string!)
// currentNumber calculation handles this:
// 0 × 10 + 0 = 0
// 0 × 10 + 1 = 1 ✓ (correct!)
// No special handling needed! ✨
🎯 Pattern Recognition - Number Formation Problems
Core Pattern: Build Value During Traversal
Template for building values from paths:
private int dfs(TreeNode node, int accumulator) {
if (node == null) return 0;
// Build/update accumulator
accumulator = transform(accumulator, node.val);
// If leaf, return accumulated value
if (leaf) {
return accumulator;
}
// Recurse and combine results
return combine(
dfs(node.left, accumulator),
dfs(node.right, accumulator)
);
}
Related Problems:
1. Path Sum (Problem 135)
Build: sum of values
Check: sum == target at leaf
Similar structure!
2. Path Sum II (Problem 151)
Build: list of values
Collect: all paths with target sum
Uses backtracking instead
3. Binary Tree Maximum Path Sum (Problem 147)
Build: path sum
Track: global maximum
Different pattern (global variable)
4. Smallest String Starting From Leaf
Build: string from path
Compare: lexicographically
Same pattern, different data type!
When to Use This Pattern:
✓ Building value incrementally
✓ Value depends on path from root
✓ Need to aggregate across all paths
✓ Accumulator parameter natural
✓ No backtracking needed (just return)
🆚 Comparison with Path Sum II (Problem 151)
Key Differences:
PATH SUM II (Problem 151):
- Collect ALL paths
- Need actual path values
- Use backtracking
- Modify list, restore state
SUM ROOT TO LEAF (Problem 152):
- Just sum numbers
- Don't need path details
- No backtracking needed
- Just pass number down
Similar goal, different requirements! 🎯
Code Comparison:
// PATH SUM II - Uses backtracking
private void dfs(TreeNode node, List<Integer> path, ...) {
path.add(node.val); // Add
if (leaf) {
result.add(new ArrayList<>(path));
}
dfs(node.left, path, ...); // Recurse
dfs(node.right, path, ...);
path.remove(path.size() - 1); // Backtrack
}
// SUM ROOT TO LEAF - No backtracking
private int dfs(TreeNode node, int currentNumber) {
currentNumber = currentNumber * 10 + node.val; // Build
if (leaf) {
return currentNumber;
}
return dfs(node.left, currentNumber) + // Recurse & combine
dfs(node.right, currentNumber);
}
Simpler when don't need full path! ✨
📝 Quick Revision Notes
🎯 Core Concept
Build numbers from root-to-leaf paths and sum them. Each path represents a multi-digit number (path [1,2,3] = 123). Use accumulator parameter to build number: currentNumber = previous × 10 + node.val. At leaf (both children null), return complete number. At internal node, return sum from left + right subtrees. No backtracking needed (just return values)!
⚡ Quick Implementation
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
public static TreeNode buildTree(Integer[] arr) {
if (arr == null || arr.length == 0 || arr[0] == null) {
return null;
}
TreeNode root = new TreeNode(arr[0]);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < arr.length) {
TreeNode current = queue.poll();
// Process left child
if (i < arr.length) {
if (arr[i] != null) {
current.left = new TreeNode(arr[i]);
queue.offer(current.left);
}
i++;
}
// Process right child
if (i < arr.length) {
if (arr[i] != null) {
current.right = new TreeNode(arr[i]);
queue.offer(current.right);
}
i++;
}
}
return root;
}
public static void print(TreeNode root) {
if (root == null) {
System.out.println("[]");
return;
}
List<String> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
result.add(String.valueOf(node.val));
queue.offer(node.left);
queue.offer(node.right);
} else {
result.add("null");
}
}
while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
result.remove(result.size() - 1);
}
System.out.println(result);
}
}
class Solution {
public int sumNumbers(TreeNode root) {
// Approach - DFS. When you put on paper, it looks simpler actually.
return sumNumbers(root, 0);
}
private int sumNumbers(TreeNode root, int currSum) {
// obvious base case, in case.
if(root == null) {
return 0;
}
// Step 1:
// When tree is like [1,2,3] where 1 is root and 2 and 3 are its left and right child.
// First time, this method gets called with root, at that time, currSum becomes 1.
// Next time, when this method gets called with 2, currSum is 1 and when below
// line gets executed, it becomes 12.
// Since, LST and RST gets called separately, separate sums will be 12 and 13.
currSum = currSum * 10 + root.val;
// Step 2:
// If this is the final node (or leaf node), just return
// In above example, when 2 is leaf node, returns 12 at the step 3.
// In case of 3, it returns 13.
if(root.left == null && root.right == null) {
return currSum;
}
// Step 3:
int left = sumNumbers(root.left, currSum); // 12 comes here when root.val is 1 (or when I am root node at the last)
int right = sumNumbers(root.right, currSum); // 13 comes here (same as above)
return left + right;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.sumNumbers(TreeNode.buildTree(new Integer[] {4,9,0,5,1})));
System.out.println(s.sumNumbers(TreeNode.buildTree(new Integer[] {1,2,3})));
}
}
🔑 Key Insights
Number Formation Formula:
Building number like reading digits left-to-right:
Path: 4 → 9 → 5
Step 1: 0 × 10 + 4 = 4 (just 4)
Step 2: 4 × 10 + 9 = 49 (forty-nine)
Step 3: 49 × 10 + 5 = 495 (four-ninety-five)
Formula: new = old × 10 + digit
Why × 10? Shifts digits left:
4 → 40 (makes room for 9)
49 → 490 (makes room for 5)
Then + digit fills the ones place! 🔑
Accumulator Pattern:
Pass value DOWN tree as parameter:
Root receives: 0
Builds: 4
Passes: 4 to children
Left child receives: 4
Builds: 49
Passes: 49 to children
Leaf receives: 49
Builds: 495
Returns: 495 (done!)
Value flows DOWN, sum flows UP! ⬇️⬆️
Return Value Meaning:
Different at each level:
Leaf node:
Returns: Complete number formed
Example: returns 495
Internal node:
Returns: Sum of all numbers in subtree
Example: returns 495 + 491 = 986
Root:
Returns: Sum of ALL root-to-leaf numbers
Example: returns 1026
Aggregation happens on the way UP! ⬆️
Why No Backtracking:
PATH SUM II needs backtracking:
- Collects actual paths
- Modifies shared list
- Must restore state
SUM ROOT TO LEAF doesn't:
- Only needs final numbers
- Number passed by value (immutable int)
- No shared state to restore
Simpler problem → Simpler solution! ✨
🎪 Memory Aid
"currentNumber = old × 10 + digit!"
"Leaf returns number, internal returns sum!"
"Pass DOWN, aggregate UP!"
"No backtracking needed!" ✨
⚠️ Don't Forget
- Multiply by 10 (not add!)
- Both children null (for leaf check!)
- Return 0 for null (contributes nothing!)
- Pass current number (to children!)
- Sum at internal nodes (left + right!)
- No backtracking (just return!)
🎉 Congratulations!
You've mastered number formation from paths!
What You Learned:
✅ Number building - Incremental formation
✅ Accumulator pattern - Pass value down
✅ Return aggregation - Sum coming up
✅ No backtracking - When not needed
✅ Leaf vs internal - Different returns
✅ Pattern comparison - vs Path Sum II
The Accumulator Pattern:
Key insight: Pass accumulated value as parameter
Benefits:
- Clean code (no global variables)
- No backtracking needed
- Natural recursion flow
- Immutable parameters
When to use:
- Building value incrementally
- Value only flows one direction
- Don't need full path details
Professional pattern! 💼
Interview Mastery:
Interviewer: "Sum all root-to-leaf numbers"
Your response:
"Build numbers incrementally as we traverse.
Key insight: Pass current number as parameter
currentNumber = previous × 10 + node.val
At leaf: Return complete number
At internal: Return sum from both subtrees
No backtracking needed since we only need
final numbers, not the actual paths.
Time: O(n), Space: O(h)"
Shows pattern understanding! 💯
You've learned when backtracking is needed vs when simpler approaches work! 🏆✨🎯