MediumNeetCode150TreeDepth-First SearchBinary Tree
Sum Root to Leaf Numbers
Sum all root-to-leaf numbers.
Examples
Input
root = [1,2,3]
Output
25
12 + 13 = 25.
Constraints
- •
Number of nodes in [1,1000] - •
0 <= Node.val <= 9
Approaches
Collect all paths, sum.
CodeT: O(n) | S: O(n) stack + paths
Build number as we go.
CodeT: O(n) | S: O(h) stack
Same approach.
CodeT: O(n) | S: O(h)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| DFS | O(n) | O(n) stack + paths | Collect all paths, sum. |
| DFS Track Sum | O(n) | O(h) stack | Build number as we go. |
| DFS Optimized | O(n) | O(h) | Same approach. |
DFS
T: O(n)S: O(n) stack + paths
Collect all paths, sum.
DFS Track Sum
T: O(n)S: O(h) stack
Build number as we go.
DFS Optimized
T: O(n)S: O(h)
Same approach.
Common Mistakes
Not building number correctly
Off-by-one in multiplication
Not handling single node