Sum the Binary Numbers Spelled by Root-to-Leaf Paths in a 0/1 Tree
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a binary tree in which every node holds the bit `0` or `1`. Each path from the root down to a leaf spells a binary number, read with the root as the most significant bit: for example, the path `1 -> 0 -> 1` spells binary `101`, which is 5. Return the sum of the numbers spelled by all root-to-leaf paths.
### Function Signature
```python
def sum_root_to_leaf_numbers(root: list[int | None]) -> int:
```
`root` is the tree in level-order form, as described under Rules.
### Rules
- Level-order form: `root[0]` is the root's value. The remaining entries are read in pairs, one pair for each non-`None` node in the order the nodes appear in the list. The first entry of a pair is that node's left child and the second is its right child; `None` means the child is absent. Trailing `None` entries may be omitted, and a node whose pair lies beyond the end of the list has no children.
- A leaf is a node with no children. Every leaf contributes exactly one path.
- Leading zeros are allowed: the path `0 -> 1 -> 1` spells binary `011`, which is 3.
- If the root has no children, the tree has a single path, and the answer is the root's bit.
### Constraints
- The tree has between 1 and 1,000 nodes, `1 <= len(root) <= 2001`, and `root[0]` is not `None`.
- Every entry other than `None` is `0` or `1`.
- Every root-to-leaf path has at most 31 nodes, so each path's number is at most `2^31 - 1`.
- The tests guarantee that the answer is at most `2^31 - 1`.
### Examples
**Example 1**
```text
Input: root = [1, 1, 0, None, 1, 1]
Output: 12
```
The root `1` has left child `1` and right child `0`. The left child has no left child and a right child `1`. The right child has a left child `1`, and its right child is omitted. The paths are `1 -> 1 -> 1` (binary `111`, which is 7) and `1 -> 0 -> 1` (binary `101`, which is 5), so the sum is 12.
**Example 2**
```text
Input: root = [1, 0, None, 0, 1]
Output: 9
```
The root has only a left child `0`, whose children are `0` and `1`. The paths spell `100` (4) and `101` (5).
**Example 3**
```text
Input: root = [0]
Output: 0
```
The root is a leaf, and its single path spells `0`.
Overview: Given a binary tree of 0 and 1 bits in level-order form, return the sum of the binary numbers spelled by every root-to-leaf path, reading the root as the most significant bit. The problem tests tree traversal, carrying an accumulated value down each path, and parsing a level-order serialization correctly.
You are given a binary tree in which every node holds the bit `0` or `1`. Each path from the root down to a leaf spells a binary number, read with the root as the most significant bit: for example, the path `1 -> 0 -> 1` spells binary `101`, which is 5. Return the sum of the numbers spelled by all root-to-leaf paths.
Implement `sum_root_to_leaf_numbers(root)`, where `root` is the tree in level-order form:
- `root[0]` is the root's value. The remaining entries are read in pairs, one pair for each non-`None` node in the order the nodes appear in the list. The first entry of a pair is that node's left child and the second is its right child; `None` means the child is absent. Trailing `None` entries may be omitted, and a node whose pair lies beyond the end of the list has no children.
- A leaf is a node with no children. Every leaf contributes exactly one path.
- Leading zeros are allowed: the path `0 -> 1 -> 1` spells binary `011`, which is 3.
- If the root has no children, the tree has a single path, and the answer is the root's bit.
An absent child is `None` in Python, `null` in JavaScript, a `null` element of the `java.util.List<Integer>` in Java, and `std::nullopt` in the `std::vector<std::optional<int>>` in C++.
Return the sum as a single integer. Every path's number and the total never exceed `2^31 - 1`, so the answer fits in a signed 32-bit integer.
### Constraints
- The tree has between 1 and 1,000 nodes, `1 <= len(root) <= 2001`, and `root[0]` is not `None`.
- Every entry other than `None` is `0` or `1`.
- Every root-to-leaf path has at most 31 nodes, so each path's number is at most `2^31 - 1`.
- The tests guarantee that the answer is at most `2^31 - 1`.
### Examples
**Example 1**
```text
Input: root = [1, 1, 0, None, 1, 1]
Output: 12
```
The root `1` has left child `1` and right child `0`. The left child has no left child and a right child `1`. The right child has a left child `1`, and its right child is omitted. The paths are `1 -> 1 -> 1` (binary `111`, which is 7) and `1 -> 0 -> 1` (binary `101`, which is 5), so the sum is 12.
**Example 2**
```text
Input: root = [1, 0, None, 0, 1]
Output: 9
```
The root has only a left child `0`, whose children are `0` and `1`. The paths spell `100` (4) and `101` (5).
Constraints
- The tree has between 1 and 1,000 nodes, 1 <= len(root) <= 2001, and root[0] is not None.
- Every entry other than None is 0 or 1.
- Every root-to-leaf path has at most 31 nodes, so each path's number is at most 2^31 - 1.
- The tests guarantee that the answer is at most 2^31 - 1.
Examples
Input: ([0],)
Expected Output: 0
Explanation: Single node 0: the root is the only leaf, so the answer is its bit (source Example 3).
Input: ([1],)
Expected Output: 1
Explanation: Single node 1: the root is the only leaf, so the answer is its bit.
Hints
- Apply the pairing rule literally: each non-None node, taken in the order it appears in the list, owns the next two unread entries as its left and right child, and an entry past the end of the list is an absent child.
- Appending one more bit to a binary number doubles it and adds the bit, so a node's number can be built from its parent's number.
- Only a node with no children ends a path; a node with exactly one child is not a leaf.