Overlay two binary trees into one by summing values at shared positions
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two binary trees. Merge them into one new binary tree by overlaying them, with the two roots aligned. Where both trees have a node at the same position, the merged tree has a node there whose value is the sum of the two values. Where only one tree has a node, the merged tree has a node there with that node's value, and everything below it comes from that tree alone. A position is identified by the sequence of left and right moves from the root.
Trees are passed and returned in level-order list form, described in the rules below.
### Function Signature
```python
def merge_trees(tree1: list[int | None], tree2: list[int | None]) -> list[int | None]:
```
### Rules
- Serialization: the first entry is the root. Then, for each non-`None` entry in list order, two later entries give its left child and its right child, with `None` for a missing child. A `None` entry has no child entries. Trailing `None` entries are omitted, and an empty tree is `[]`.
- Return the merged tree in the same serialization, which makes the answer unique.
- A merged node whose summed value is `0` is still a node. Only positions that are absent from both trees are missing from the result.
### Constraints
- Each tree has between `0` and `10^4` nodes.
- Every node value is an integer in `[-10^6, 10^6]`, so every merged value lies in `[-2 * 10^6, 2 * 10^6]`.
- Each input list is a valid serialization as described above.
- A tree may be completely unbalanced, so its depth can equal its number of nodes.
### Examples
**Example 1**
```text
Input: tree1 = [4, 2, 6, 1], tree2 = [1, None, 3, None, 5]
Output: [5, 2, 9, 1, None, None, 5]
```
The roots overlay to `4 + 1 = 5`, and the right children to `6 + 3 = 9`. The left subtree `2` with left child `1` exists only in `tree1`, and the right child `5` below `3` exists only in `tree2`.
**Example 2**
```text
Input: tree1 = [], tree2 = [7, 8]
Output: [7, 8]
```
**Example 3**
```text
Input: tree1 = [-1, None, 2], tree2 = [1, 3]
Output: [0, 3, 2]
```
The roots sum to `0`, which is still a node. The left child `3` comes only from `tree2`, and the right child `2` only from `tree1`.
Overview: Merge two binary trees by overlaying them from the root: positions present in both trees become one node holding the sum of the two values, and positions present in only one tree keep that tree's node. It tests simultaneous tree traversal, handling of missing children and level-order serialization.