Sum Root to Leaf Numbers — Solution

Problem

Given a binary tree where every node contains a single digit (0–9), each root-to-leaf path spells out a number by concatenating the digits from top to bottom. Return the total sum of all these path numbers.

[4,9,0,5,1]

• Input: root = [4, 9, 0, 5, 1]
• Output: 1026
• Explanation: The three paths are 4→9→5 = 495, 4→9→1 = 491, and 4→0 = 40, summing to 1026.

A simpler example with root = [1, 2, 3] gives paths 1→2 = 12 and 1→3 = 13, totaling 25.

Intuition

Each path from root to leaf forms a multi-digit number where the root contributes the most significant digit. As you go deeper, the accumulated value shifts one decimal place left — the same operation as parsing a number digit by digit. Only a true leaf (no children at all) marks the end of a complete path number that can be added to the total.

Solution — DFS

Perform a depth-first traversal while carrying the number built so far. At each node, shift the running total left one decimal place and add the node's digit. Once a leaf is reached, the number is complete and counts toward the answer.

1. Define a recursive helper that takes the current node and the number accumulated on the path so far.
2. If the node is null, return 0 — this handles missing children without special cases above.
3. Extend the running number: current_number = current_number * 10 + node.val.
4. If the node is a leaf (both children are null), return current_number — the path is complete.
5. Otherwise, recurse on both subtrees and return the sum of their results.
6. Kick off the helper on the root with an initial value of 0.

1class Solution:
2    def sumNumbers(self, root: Optional[TreeNode]) -> int:
3        def dfs(node, current_number):
4            if not node:
5                return 0
6            current_number = current_number * 10 + node.val
7            if not node.left and not node.right:  # leaf: path is complete
8                return current_number
9            return dfs(node.left, current_number) + dfs(node.right, current_number)
10
11        return dfs(root, 0)

Time: O(n) — every node is visited exactly once.

Space: O(h) — the call stack is as deep as the tree's height; O(n) worst case for a skewed tree, O(log n) for a balanced one.

Complexity Summary

Common Mistakes

• Treating a one-child node as a leaf — a leaf requires both children to be null. Returning current_number when only one child is null cuts off valid paths and under-counts the total.
• Adding instead of shifting — writing current_number + node.val instead of current_number * 10 + node.val sums digits rather than building a decimal number, producing a completely wrong result.
• Accumulating paths in a mutable list without backtracking — if you append digit-by-digit to a shared list and forget to pop after recursing, later paths pick up stale digits from earlier ones.
• Checking for null before multiplying — some solutions guard if node is None: return 0 at the top but then never reach the leaf check for a node that has exactly one null child, accidentally counting internal nodes as leaves.
• Integer overflow on very deep trees — nodes can have values 0–9 and paths can be arbitrarily long; at depth 13 the running number can exceed a 32-bit int. Use long in Java for safety; Python integers are unbounded.

Related Problems

• Path Sum — same root-to-leaf DFS structure, but checks whether the accumulated sum equals a target instead of returning its decimal value
• Path Sum II — collect every root-to-leaf path whose node sum matches a target, requiring explicit path tracking with backtracking
• Path Sum III — paths that don't have to start at the root or end at a leaf, demanding a prefix-sum approach on top of tree DFS
• Binary Tree Maximum Path Sum — maximise the sum across any path through the tree, requiring each DFS call to return only the best single-branch contribution
• Binary Tree Right Side View — BFS or DFS to collect one value per depth level, practicing the same "carry state through traversal" pattern