Sum Root to Leaf Numbers
Medium · Trees · Tree · Depth-First Search · Binary Tree
Problem
Every node of a binary tree holds a single digit from 0 to 9. Each root-to-leaf path spells a number by reading its digits from the top down: the path 4 → 0 → 7 spells 407.
Given the root, return the sum of all the numbers spelled by root-to-leaf paths. A leaf is a node with no children. The tests keep the answer within a 32-bit signed integer.
The tree is given in level order, with None for a missing child. from_level([4,0,7,5]) builds it and to_level(root) turns it back into a list.
Examples
Input: root = [4,0,7,5] Output: 452
The paths spell 405 (4 → 0 → 5) and 47 (4 → 7). 405 + 47 = 452.
Input: root = [2,3,8] Output: 51
The paths spell 23 and 28. 23 + 28 = 51.
Input: root = [7] Output: 7
The root is a leaf, so the only number is 7.
Constraints
- 1 <= number of nodes <= 1000
- 0 <= Node.val <= 9
- the tree has at most 10 levels
- the answer is less than 2^31
Approaches
- Collect every path as text, then add them up — time O(n · h), space O(n · h)
Follow-up
The stack holds one pending node per level, so the extra space is O(h). Can you do it in O(1) extra space? (A Morris traversal can, by undoing the digits it added when it climbs back up a temporary link.)
Related problems
Start free on Cariara · Coding problems · System design studio
