dsa · easy

Merge Two Binary Trees

Merge root1 and root2 by overlapping them from the roots down. When two nodes occupy the same position, the merged node’s value is the sum of those two values, and you merge their left children together and their right children together. When only one tree has a node at a position, keep that node (and its whole remaining subtree).

Arguments

• root1 — first tree as nested [val, left, right] or None
• root2 — second tree in the same encoding

Each node is [val, left, right] or None. Return the merged tree in the same encoding.

Example

root1 = [1, [3, [5, None, None], None], [2, None, None]], root2 = [2, [1, None, [4, None, None]], [3, None, [7, None, None]]].

Roots 1 + 2 = 3. Left children 3 + 1 = 4; that node keeps 5 from the first tree and 4 from the second. Right children 2 + 3 = 5, with a right grandchild 7 from the second tree. The merged tree is [3, [4, [5, None, None], [4, None, None]], [5, None, [7, None, None]]].

Constraints

Number of nodes in [0, 2000] per tree -10^4 <= val <= 10^4 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
[1, [3, [5, None, None], None], [2, None, None]]
[2, [1, None, [4, None, None]], [3, None, [7, None, None]]]

Expected:
[3,[4,[5,null,null],[4,null,null]],[5,null,[7,null,null]]]

Example 2

Input:
[1, None, None]
None

Expected:
[1,null,null]

Open in the Dojo editor