#617

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Merge Two Binary Trees

Merge Two Binary Trees requires combining nodes by summing overlapping values while preserving non-null nodes from either tree efficiently.

tree depth first search breadth first search binary tree

Problem Statement

You are given two binary trees, root1 and root2. Your task is to combine them into a new tree by following a specific merge rule: for overlapping nodes, add their values to create the new node; for nodes that exist in only one tree, use that node as-is.

Return the resulting merged binary tree. The input trees may be empty or unbalanced, and your solution must handle both DFS and BFS traversal patterns to track node states correctly while preserving the binary tree structure.

Examples

Example 1

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]

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

Example details omitted.

Example 2

Input: root1 = [1], root2 = [1,2]

Output: [2,2]

Example details omitted.

Constraints

The number of nodes in both trees is in the range [0, 2000].
-104 <= Node.val <= 104

Solution Approach

Recursive Depth-First Merge

Use a recursive DFS to traverse both trees simultaneously. At each node, if both exist, sum the values and recursively merge left and right children. If one node is null, return the other node to preserve its subtree.

Iterative BFS Merge with Queue

Use a queue to track pairs of nodes from both trees. For overlapping nodes, sum values and enqueue their children for further merging. If a node in one tree is null, attach the non-null node to the merged tree directly.

Edge Case Handling

Check for null root inputs before starting traversal. Handle unbalanced trees by returning non-null subtrees. Ensure your recursive or iterative method does not overwrite existing nodes improperly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(min(N1,N2)) where N1 and N2 are the number of nodes in root1 and root2 since each pair is processed once. Space complexity is O(H) for DFS recursion stack or O(W) for BFS queue, with H as tree height and W as maximum width of the trees.

What Interviewers Usually Probe

Do you handle null nodes correctly during traversal?
Can you explain why DFS and BFS both work for merging trees?
How do you manage space when merging large unbalanced trees?

Common Pitfalls or Variants

Common pitfalls

Forgetting to return non-null nodes when the other tree has null children.
Overwriting existing subtrees instead of summing overlapping nodes.
Ignoring edge cases with completely empty input trees.

Follow-up variants

Merge multiple binary trees instead of two, generalizing DFS/BFS merging.
Merge trees but keep maximum value instead of sum at overlapping nodes.
Perform merge while maintaining additional attributes per node, like color or weight.

FAQ

What is the main idea behind Merge Two Binary Trees?

Traverse both trees simultaneously, sum values for overlapping nodes, and keep non-null nodes when only one exists.

Should I use DFS or BFS to merge two binary trees?

Both DFS and BFS work; DFS is simpler recursively, BFS works iteratively and helps visualize level-wise merging.

How do I handle empty input trees?

If one or both roots are null, return the non-null root or null if both are empty, ensuring the merge is valid.

Can this method handle unbalanced trees?

Yes, by recursively or iteratively checking for null children, you can merge unbalanced trees without losing any subtree.

Does GhostInterview track the Binary-tree traversal pattern?

Yes, it highlights traversal and state tracking, helping you avoid common mistakes when merging overlapping and non-overlapping nodes.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(
        self, root1: Optional[TreeNode], root2: Optional[TreeNode]
    ) -> Optional[TreeNode]:
        if root1 is None:
            return root2
        if root2 is None:
            return root1
        node = TreeNode(root1.val + root2.val)
        node.left = self.mergeTrees(root1.left, root2.left)
        node.right = self.mergeTrees(root1.right, root2.right)
        return node

Continue Practicing

#623 add one row to tree #637 average of levels in binary tree #653 two sum iv input is a bst