Sum Numbers Formed by Root-to-Leaf Paths

Problem Statement

You are given a binary tree represented as an array (heap array representation) where the root is at index 0. For any node at index i:

• Its left child is at index 2 * i + 1.
• Its right child is at index 2 * i + 2.

Each node contains a decimal digit from 0 to 9. Missing nodes are represented by None. Any index beyond the end of the array is also considered a missing node.

A root-to-leaf path represents a decimal integer formed by concatenating the digits from the root down to the leaf node (e.g., a path 1 -> 2 -> 3 forms the number 123). A leaf is a valid node that has neither a left child nor a right child.

Write a function that calculates and returns the sum of all numbers formed by root-to-leaf paths.

Function Signature

def sum_root_to_leaf(tree: list[int | None]) -> int:
    pass

Examples

Example 1

Input: tree = [1, 2, 3]
Output: 25
Explanation:
The tree is:
    1
   / \
  2   3
Path 1 -> 2 forms the number 12.
Path 1 -> 3 forms the number 13.
Total sum = 12 + 13 = 25.

Example 2

Input: tree = [4, 9, 0, 5, 1]
Output: 1026
Explanation:
The tree is:
      4
     / \
    9   0
   / \
  5   1
Path 4 -> 9 -> 5 forms 495.
Path 4 -> 9 -> 1 forms 491.
Path 4 -> 0 forms 40 (0 is a leaf here since it has no children).
Total sum = 495 + 491 + 40 = 1026.

Constraints

• 0 <= len(tree) <= 2 * 10^4
• tree[i] is either an integer in the range [0, 9] or None.
• The root tree[0] is guaranteed to be a valid digit if the array is non-empty.
• The answer is guaranteed to fit within a standard 64-bit signed integer.

Edge Cases

• An empty input array should return 0.
• A single root node with no children returns the root's value itself.
• Nodes with only one child must continue along that path; they are not leaves.