Digit Trails Total
MediumTrees
Problem
Every node of a binary tree holds one digit from 0 to 9. Reading the digits along a root-to-leaf trail gives a number: the trail 4 → 9 → 5 spells 495.
Given the root of a non-empty tree, return the sum of the numbers spelled by all root-to-leaf trails.
Example 1
- Input:
- root = [1, 2, 3]
- Output:
- 25
12 + 13 = 25.
Example 2
- Input:
- root = [4, 9, 0, 5, 1]
- Output:
- 1026
495 + 491 + 40 = 1026.
Constraints
- 1 ≤ number of nodes ≤ 1023
- 0 ≤ node.val ≤ 9
- Tree height ≤ 10, so every number fits easily in a 64-bit integer.
Hint
Show the first hint
How does the number change when you append one more digit to the right?
Walkthrough
How to approach it
01Clarify before coding
- Do leading zeros matter? A trail 0 → 5 spells 5; the arithmetic handles it.
- Only root-to-leaf trails? Yes, inner nodes do not end a number.
- How big can numbers be? At most 10 digits, so 64-bit integers (and JavaScript doubles, exact up to 2^53) are safe.
02Brute force
Collect each trail as a string of digits, convert to an integer at the leaf and add up.
Cost: O(n · h) time because each leaf rebuilds a string of length h.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.