Sum Root to Leaf Numbers
Each root-to-leaf path spells a number; return the sum of all such numbers.
- 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.
Intuition
Sum root to leaf numbers treats every root-to-leaf path as a number — a path through nodes 1, 2, 3 spells 123 — and asks for the total across all paths.
Two approaches technically work but miss something. Building a string along the path and parsing it at each leaf is correct but wasteful. Summing digits individually is simply wrong, since place value matters.
The clean version carries the number itself down the recursion:
- cur = cur * 10 + node.val — the multiply-by-ten is the place-value shift, done arithmetically rather than through string building.
At every node, cur holds exactly the number spelled by the path from the root to here. When a leaf is reached, that value is a complete root-to-leaf number and gets added to the total.
The one rule to be careful about is where a path ends. It terminates at a leaf — a node with no children — not at a null pointer. Testing at null would count a node with exactly one child as an ending, adding a number for a path that stops in mid-air.
Because cur is passed by value, each subtree gets its own copy and extends it independently. There is no need to undo anything on the way back up, which is what makes this cleaner than the string-building version where the append must be reversed.
Carry the running number down as a parameter, building it with cur * 10 + node.val. Adding to the total only at leaves is what makes each complete root-to-leaf path count exactly once — internal nodes contribute nothing on their own.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(h) space.
Carry the running number down
At each node compute cur = cur * 10 + node.val, the number spelled from the root to here. The multiplication is the place-value shift — this is what string concatenation was imitating, done directly.
Return zero on a null node
A null contributes nothing to the total. Handling it at the top of the function means the caller need not check whether each child exists before recursing.
Total only at leaves
If the node has neither child, cur is a complete root-to-leaf number — return it. Testing for a leaf rather than for null is essential: a null test would count a one-child node as a path ending.
Sum both subtrees
Return the sum of the two recursive calls, each passed the updated cur. Every path is counted exactly once because each leaf is reached by exactly one route from the root.
Note that no backtracking is needed
cur is passed by value, so each subtree extends its own copy independently. Nothing has to be undone on the way back up, unlike the string-building version where the appended character must be removed.
Cost of the traversal
Every node is visited once with O(1) arithmetic, giving O(n) time. Space is O(h) for the recursion stack — O(log n) balanced, O(n) on a degenerate chain.
Solution & live demo
Common pitfalls
Adding at every node
total += cur
if not node.left and not node.right:
total += curOnly complete paths ending at a leaf form a number. Accumulating at internal nodes adds every prefix — 1, 12, 123 instead of just 123.
Building the number with string concatenation
cur = cur + str(node.val) total += int(cur)
cur = cur * 10 + node.val
Allocates a string per node and parses it at every leaf. The arithmetic form is one multiply-add and never leaves integer space.
Mutating a shared running value
self.cur = self.cur * 10 + node.val dfs(node.left); dfs(node.right)
dfs(node.left, cur) dfs(node.right, cur)
A shared field carries the left subtree's digits into the right subtree unless explicitly undone on the way back up. Passing cur as a parameter gives each branch its own copy for free.
Edge cases
Return 0, no paths exist.
That node is itself both root and leaf; its value is the sum.
cur starts at 0*10+0=0, still correct -- leading zero paths are fine since LeetCode guarantees no path represents a number with a leading zero beyond the root itself.
cur grows correctly at each level via the *10 shift regardless of tree shape.