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.
You are given two binary trees, `tree1` and `tree2`. Merge them into one new binary tree by overlaying them, with the two roots aligned. A position is identified by the sequence of left and right moves from the root.
- 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 merged node whose summed value is `0` is still a node. Only positions that are absent from both trees are missing from the result.
Trees are passed and returned in level-order list form. 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 `[]`. (`None` is `null` in JavaScript and Java, and `std::nullopt` in C++.)
Return the merged tree in the same serialization. Because trailing `None` entries are omitted, the answer is unique.
**Example 1**
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**
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`.
**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]`. No value can exceed `2^31 - 1`, so a 32-bit `int` is enough in every language.
- 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.
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]; no value can exceed 2^31 - 1, so a 32-bit int is enough in every language.
- Each input list is a valid level-order serialization as described: a None entry has no child entries, trailing None entries are omitted, and an empty tree is [].
- A tree may be completely unbalanced, so its depth can equal its number of nodes.
Examples
Input: ([4, 2, 6, 1], [1, None, 3, None, 5])
Expected Output: [5, 2, 9, 1, None, None, 5]
Explanation: Source example 1: roots 4 + 1 = 5 and right children 6 + 3 = 9; the subtree 2 -> 1 exists only in tree1 and the right child 5 below 3 only in tree2.
Input: ([-1, None, 2], [1, 3])
Expected Output: [0, 3, 2]
Explanation: Source example 3: the roots sum to 0, which is still a node; left child 3 comes from tree2 and right child 2 from tree1.
Hints
- A position is the sequence of left and right moves from the root, so first recover which entry is the left or right child of which node; remember that a None entry has no child entries of its own.
- Where only one tree has a node, everything below it comes from that tree alone; positions missing from both trees stay missing, while a summed value of 0 is still a node.
- A tree can be a single chain as deep as its node count, and the returned list must omit trailing None entries while keeping interior ones.