Sum Numbers Formed by Root-to-Leaf Paths
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement `sum_root_to_leaf_numbers(values)` for a binary tree serialized as a zero-based heap array. For an existing node at index `i`, its children are at `2 * i + 1` and `2 * i + 2`. A `null` slot means no node, and an existing node never appears below a missing parent. Every existing value is a decimal digit from `0` through `9`.
Each root-to-leaf path forms a number by concatenating its digits from root to leaf. Return the sum of all such numbers. A leaf has no existing left or right child, and an empty serialization returns `0`.
For example, a root `1` with children `2` and `3` forms `12` and `13`, so the result is `25`.
```hint Carry the prefix numerically
When visiting digit `d` with accumulated prefix `p`, the new prefix is `p * 10 + d`.
```
```hint Add only at leaves
Internal prefixes are not complete path numbers. Contribute the accumulated value only when both children are absent.
```
### Discussion Extensions
- How would an iterative depth-first traversal avoid recursion depth limits on a very deep tree?
- What is the time complexity in terms of nodes and the auxiliary space in terms of tree height?
Quick Answer: Sum all numbers formed by root-to-leaf digit paths in a binary tree represented as a heap array. Carry each decimal prefix through the traversal, add only at leaves, and analyze recursive versus iterative space.
Implement sum_root_to_leaf_numbers(values) for a binary tree serialized as a zero-based heap array with null slots and decimal-digit node values. Concatenate digits along every root-to-leaf path and return the sum of the resulting numbers; return zero for an empty tree.
Constraints
- 0 <= values.length <= 255, and an existing node never appears below a null parent.
- Each existing node value is a decimal digit from 0 through 9.
- The final sum fits in a signed 64-bit integer.
Examples
Input: ([1, 2, 3],)
Expected Output: 25
Input: ([4, 9, 0, 5, 1],)
Expected Output: 1026
Hints
- Carry a numeric prefix and update it as prefix * 10 + digit when visiting a node.
- Add a prefix only when neither serialized child index contains an existing node.