Merge two binary trees by combining overlapping nodes and keeping non-null branches.
Merge Two Binary Trees
You are given two binary trees. Create a new binary tree by merging them together with the following rule:
- If two nodes overlap, their values are added together.
- If only one node exists at a position, use that node directly in the merged tree.
- If both nodes are null, the merged result is null.
Return the root of the merged tree.
The merge should preserve the tree structure wherever possible.
Input Format
- Two binary tree roots,
root1androot2. - Each tree node contains an integer value and optional left/right children.
Output Format
- Return the root of the merged binary tree.
Constraints
- The trees may be empty.
- Node values can be positive, negative, or zero.
- The merged tree must contain the sum of overlapping nodes.
- The exact node count is bounded by the total nodes across both input trees.
Example 1
Input
root1 = [1,3,2,5] root2 = [2,1,3,null,4,null,7]
Output
[3,4,5,5,4,null,7]
Explanation
The roots overlap, so 1 + 2 = 3. Merge the left children 3 and 1 into 4, the right children 2 and 3 into 5, and continue recursively for lower levels.
Example 2
Input
root1 = [1] root2 = [1,2]
Output
[2,2]
Explanation
The root values add to 2. The left child exists only in the second tree, so it is kept directly.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.