Sum root-to-leaf numbers in a digit tree

Each node of a binary tree holds a digit from 0 to 9, so every path from the root to a leaf spells a number (root digit first). Return the sum of all those numbers.

Interface

Unless you agree on a different interface with the interviewer, assume:

• sum_numbers(tree: list[int | None]) -> int — the tree is stored like a heap array: the children of index i are at 2i + 1 and 2i + 2, and None marks a missing node. An empty array sums to 0.

Example

sum_numbers([1, 2, 3])           ->  25     # 12 + 13
sum_numbers([4, 9, 0, 5, 1])     ->  1026   # 495 + 491 + 40
sum_numbers([1, 0, None, 2])     ->  102    # one path 1 -> 0 -> 2

Constraints

• Up to 1,000 nodes; depth at most 10, so every number fits in a 32-bit integer.
• A leaf is a node with no children; a node with one child is not a leaf.

Clarifying questions

• How is the tree given: nodes, or an array? If an array, heap-indexed or level-order?
• What counts as a leaf when a node has only one child?
• Can the numbers overflow?
• Is an empty tree possible?

What a strong answer covers

• DFS carrying the number so far: current = current * 10 + digit, adding it to the total only at a leaf. O(n) time.
• Correct leaf detection in the array form: a child index past the end or holding None is missing.
• Recursive versus iterative: recursion uses O(h) stack; an explicit stack of (index, current) pairs avoids recursion limits.
• Tests: a single node, a node with only one child, a zero digit, an empty tree.

Follow-ups

• Return the largest root-to-leaf number instead of the sum.
• The tree is very deep, so numbers overflow: return the sum modulo 10^9 + 7.
• Do it in O(1) extra space (Morris traversal).