Sum of Root to Leaf Numbers
Mahabharata — The Decimal Paths — Each Root-to-Leaf Path Forms a Number, Sum Them All
मूल से पत्ती तक — एक संख्या। हर कदम: num = num×10 + val; पत्ती पर जोड़ो॥
*Root to leaf — forms a number. Each step: num = num×10 + val; add at leaf.*
The Story
Each root-to-leaf path forms a number by concatenating the node values as digits. Return the sum of all these numbers.
For tree `[1,2,3]`: paths are 1→2=12 and 1→3=13. Sum=25. For `[4,9,0,5,1]`: paths 4→9→5=495, 4→9→1=491, 4→0=40. Sum=1026.
**DFS with running number:** - At each node: `num = num * 10 + root.val` - At leaf: add `num` to total - Recurse left and right
```java public int sumNumbers(TreeNode root) { return dfs(root, 0); } int dfs(TreeNode root, int num) { if (root == null) return 0; num = num * 10 + root.val; if (root.left == null && root.right == null) return num; // Leaf: return path number return dfs(root.left, num) + dfs(root.right, num); } ```
Trace `[1,2,3]`: - dfs(1, 0): num=1. Not leaf. return dfs(2,1)+dfs(3,1) - dfs(2, 1): num=12. Leaf → return 12 - dfs(3, 1): num=13. Leaf → return 13 - Total: 12+13=25 ✓
Trace `[4,9,5]`: - dfs(4,0): num=4. dfs(9,4)+dfs(null,4) - dfs(9,4): num=49. dfs(5,49) - dfs(5,49): num=495. Leaf → 495 - dfs(null,4) = 0. Total from right. - Sum = 495 (if only 4→9→5 path)
The Path Collection + String Parse
Collect path as string at each leaf, convert to int, sum all. O(n) but extra string allocation.
int total = 0;
void dfsString(TreeNode root, String path) {
if (root == null) return;
path += root.val;
if (root.left == null && root.right == null) {
total += Integer.parseInt(path);
return;
}
dfsString(root.left, path);
dfsString(root.right, path);
}The num×10+val Decimal Building Wisdom
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
int dfs(TreeNode root, int num) {
if (root == null) return 0;
num = num * 10 + root.val;
if (root.left == null && root.right == null) return num;
return dfs(root.left, num) + dfs(root.right, num);
}Step-by-Step Walkthrough
Single node [5]: dfs(5,0). num=5. Leaf → return 5. Total=5 ✅
Deep Insight
**The num*10 trick:** Concatenating digits by multiplying by 10 is the standard integer digit-building technique (also used in rb-4 digit problems, just reversed: n%10 extracts, n*10+d builds).
**Overflow consideration:** If the tree is deep (many digits), num can overflow int. Use long.
**Parameter propagation:** The `num` parameter is passed by value — each recursive branch gets its own copy. This means no backtracking needed! The path number accumulates as we descend, and each leaf directly has the correct path number.
**Elegant dual-purpose leaf check:** `dfs(null) = 0` handles missing children. The leaf check `left==null && right==null` triggers the return of the complete path number.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | String allocation per path |
| Optimal | O(n) | O(h) | In-place num computation; O(h) call stack |
Pattern Recognition
✅ Root-to-leaf numbers: num = num*10 + root.val at each node ✅ At leaf: return num (complete path number) ✅ Sum: dfs(left) + dfs(right) ✅ No backtracking needed (num passed by value) **LeetCode Trigger Phrases:** → "sum root to leaf numbers" → Each path forms a number → Decimal digit accumulation in DFS
Bhagavad Gita 10.8
अहं सर्वस्य प्रभवो मत्तः सर्वं प्रवर्तते। इति मत्वा भजन्ते मां बुधा भावसमन्विताः॥
I am the origin of all things; from Me everything proceeds. Knowing this, the wise worship Me with devotion.
Connection: Each path from root to leaf represents a unique number — the root's digit is most significant, the leaf's digit least significant. Like all of creation emerging from the divine root (each manifestation a unique path from the source), each root-to-leaf path forms a unique number built by multiplying by 10 (ascending through the hierarchy) and adding the next digit. The sum of all path numbers is the tree's total numerical expression.