Overlay two binary trees into one by summing values at shared positions

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

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

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 = [], tree2 = [7, 8]
Output: [7, 8]

Example 3

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.

Overlay Two Binary Trees in Level-Order Form

Hints

1. 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.
2. 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.
3. 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.

Approach

Parse each list into parallel arrays of node values and left/right child indices, without recursion. The k-th non-None entry is the k-th node, and the entries after the root are consumed two at a time (left slot, then right slot) for each node in creation order; a None entry creates no node and so owns no slots, which is exactly the source rule. A list that ends early simply leaves the remaining slots empty, matching the omitted trailing None entries.

Then run a breadth-first traversal over pairs (a, b), where a is a node of tree1 or absent and b is a node of tree2 or absent, starting from the pair of roots. For each dequeued pair, examine its left child pair and then its right child pair: if both sides are absent, append None; otherwise append the sum of the values that are present and enqueue the pair. Finally drop trailing None entries.

Invariant: the queue holds the merged nodes in level order, and every merged node emits exactly two child slots in that order, so the emitted list is precisely the level-order serialization of the merged tree. Correctness: a merged position exists exactly when at least one side of its pair is present, its value is the sum of the present values (a sum of 0 is still emitted as a node), and a subtree that exists in only one tree is copied whole because every pair below it keeps the other side absent.

Edge cases: both trees empty returns []; one empty tree returns a copy of the other; merged values stay within [-2 * 10^6, 2 * 10^6], so 32-bit integers suffice; the work is iterative, so a completely unbalanced tree up to 10^4 deep cannot overflow the call stack.

• Time complexity: O(n + m), where n and m are the lengths of tree1 and tree2
• Space complexity: O(n + m)