#129 Sum Root to Leaf Numbers

frequently reported atMeta Google Amazon Microsoft

the problem

In plain words

Every node holds one digit, 0 to 9. Reading a root-to-leaf path from top to bottom spells a number: 1 → 2 → 3 spells 123. Return the sum of the numbers spelled by all root-to-leaf paths. The answer fits in a 32-bit int.

in root = [1,2,3]

out 25

12 + 13.

in root = [4,9,0,5,1]

out 1026

495 + 491 + 40.

1 ≤ number of nodes ≤ 1000
0 ≤ Node.val ≤ 9
Depth of the tree ≤ 10

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTree DFS (top-down)

Appending a digit is number * 10 + digit. So pass the number spelled so far down, and let each leaf return its finished number up.

solutions

From brute force to optimal

Build each path's digits in a StringBuilder, store the string at every leaf, then parse and add them all.

Append the digit, recurse, delete the last character.
At a leaf, store digits.toString().
Integer.parseInt every stored string and add.

timeO(n·h)

Each leaf copies and parses a string of up to h digits.

spaceO(n·h)

All the stored strings (h ≤ 10 here, so it stays small — but it's wasted work).

javajava.util.*

1class Solution {2    public int sumNumbers(TreeNode root) {3        List<String> numbers = new ArrayList<>();4        collect(root, new StringBuilder(), numbers);5        int total = 0;6        for (String number : numbers) total += Integer.parseInt(number);   // parse every path from scratch7        return total;8    }9 10    /** Writes each root-to-leaf path's digits as a string. */11    private void collect(TreeNode node, StringBuilder digits, List<String> numbers) {12        if (node == null) return;13        digits.append(node.val);14        if (node.left == null && node.right == null) numbers.add(digits.toString());15        collect(node.left, digits, numbers);16        collect(node.right, digits, numbers);17        digits.deleteCharAt(digits.length() - 1);           // undo before going back up18    }19}

sum(node, above) = the total for this subtree, given the number spelled by the path above it.

null → 0.
number = above * 10 + node.val.
Leaf → return number.
Else return sum(left, number) + sum(right, number).

timeO(n)

One visit per node, O(1) work each.

spaceO(h)

Recursion stack — at most 10 frames here.

javajava.util.*

1class Solution {2    public int sumNumbers(TreeNode root) {3        return sum(root, 0);4    }5 6    /** Sum of the numbers in this subtree, given the number spelled by the path above it. */7    private int sum(TreeNode node, int above) {8        if (node == null) return 0;                                   // no path ends here9        int number = above * 10 + node.val;                           // append one digit10        if (node.left == null && node.right == null) return number;   // a leaf completes the number11        return sum(node.left, number) + sum(node.right, number);12    }13}

in the room

How to say it in the interview

talk track

Show both directions in one tiny function: digits flow down (number * 10 + digit), finished numbers flow up.
Say why int is safe: the problem promises the answer fits in 32 bits; otherwise carry a long.

traps

Adding the number at null instead of at a leaf: a node with one child would add its number once for its empty side.
Building each number as a String and parsing it: extra O(h) work per leaf for nothing — above * 10 + digit does it in O(1).

what they ask next

Follow-ups

What if the numbers could exceed int?

Carry a long, or work modulo 1,000,000,007 if the problem asks for it.

Sum of Root To Leaf Binary Numbers (LC 1022)?

The same walk in base 2: number = number * 2 + bit, or (number << 1) | bit.

before you submit

Edge cases to test

One node → its own digit.
A leading zero: [0,1] → 1.
A node with one child adds nothing for its empty side: [1,null,2] → 12.

practise next