Sum Root to Leaf Numbers

Each root-to-leaf path in a binary tree forms a number by concatenating node digits. Return the sum of all such numbers.

Why this is worth learning

The recursive state is the numeric value of the entire root-to-parent digit prefix. Extending by one digit is multiplication by ten plus that digit.

Before coding: one-minute experiment

For root 1 with leaf children 2 and 3, why is the answer 25 rather than 6?

Function signature

func SumNumbers(root *TreeNode) int

Inputs / outputs

• root: root of the tree (may be nil).
• Return: sum of all root-to-leaf numbers.

Example

Tree: [1,2,3]
Numbers: 12 and 13
Output: 25

Constraints

• 0 <= number of nodes <= 100_000
• Node values are digits 0-9.
• The mathematical sum of all root-to-leaf numbers is guaranteed to fit the target Go int.

Core idea (near-solution)

One baseline constructs each leaf's digit string and parses it. The representation has a simpler incremental update: appending digit d to prefix value v produces 10v+d. Pass that number by value to each branch so siblings extend the same original prefix independently. A leaf contributes the completed number; an absent child contributes nothing, not another copy of the prefix. Summing child results counts each actual leaf once. The finite-width guarantee must cover completed path values and their total, not just individual digits.

Invariant: val equals the number formed by the path from root to the current node.

Algorithm (step-by-step)

1. DFS (node, val):
   • If node is nil, return 0.
   • val = val*10 + node.Val.
   • If node is a leaf, return val.
   • Return sum of left and right DFS calls.
2. Start with (root, 0).

Correctness sketch

Assume prefix equals the number spelled by the path before the current node. Computing prefix*10+digit appends the current decimal digit and therefore gives the number for the extended path. At a leaf, this is one complete root-to-leaf number and is returned exactly once. At an internal node, complete paths partition into those entering the left child and those entering the right, so summing their results counts every path once without overlap. A nil subtree contributes zero. Structural induction proves the result whenever all arithmetic is representable in the retained int interface.

Trace (hand walkthrough)

Example input:
Tree: [1,2,3]
Numbers: 12 and 13
Output: 25

Walk:
- Start at root 1 with val = 0 -> val = 1.
- Go left to 2: val = 12 (leaf) contributes 12.
- Go right to 3: val = 13 (leaf) contributes 13.
- Sum = 12 + 13 = 25.

Pitfalls to avoid

• Treating non-leaf nodes as complete numbers.
• Forgetting to multiply by 10 before adding the digit.

Debugging lens

Test leading zero digits, one-sided trees, and several leaves sharing a long prefix. The published node-count bound alone does not ensure a 32-bit or 64-bit result.

Complexity

• Time: O(n).
• Extra space: O(h) recursion depth.

Implementation notes (Go)

• Use integer arithmetic under the stated total-sum guarantee. Node-count and digit bounds alone do not imply representability.

Contract precision

All digits and path numbers are nonnegative. Every path prefix is at most its completed leaf number, and every subtree total is at most the overall total, so the answer guarantee also bounds the intermediate values. The function does not report overflow for unsupported inputs.

Reconstruction checkpoint

A root 2 has left leaf 0 and right child 3 with left leaf 4. Give the prefix state at node 3 and the two numbers being added. What does an absent child contribute?

Return to Binary Tree General · Module quiz