Merge Two Binary Trees

Difficulty: Easy | Acceptance: 79.10% | Paid: No Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

• Examples
• Constraints
• Recursive Depth-First Search
• Iterative Breadth-First Search

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 2:

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

Constraints

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

Recursive Depth-First Search

Intuition We traverse both trees simultaneously. If a node exists in one tree but not the other, we use the existing node. If nodes exist in both, we sum their values.

Steps

• If root1 is null, return root2.
• If root2 is null, return root1.
• Update root1’s value by adding root2’s value.
• Recursively merge the left children of both trees.
• Recursively merge the right children of both trees.
• Return the modified root1.

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1:
            return root2
        if not root2:
            return root1
        root1.val += root2.val
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)
        return root1

Complexity

• Time: O(min(m, n)) where m and n are the number of nodes in the two trees.
• Space: O(min(m, n)) for the recursion stack in the worst case (skewed tree).
• Notes: Modifies root1 in place.

Iterative Breadth-First Search

Intuition We use a queue to process nodes level by level. We push pairs of corresponding nodes from both trees into the queue and merge them iteratively.

Steps

• If both roots are null, return null.
• Initialize a queue with the pair (root1, root2).
• While the queue is not empty:
  • Pop a pair (node1, node2) from the queue.
  • If node1 is null or node2 is null, continue.
  • Sum the values: node1.val += node2.val.
  • If node1.left is null, assign node2.left to it. Otherwise, push (node1.left, node2.left) to the queue.
  • If node1.right is null, assign node2.right to it. Otherwise, push (node1.right, node2.right) to the queue.
• Return root1.

from collections import deque

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1:
            return root2
        if not root2:
            return root1
        queue = deque([(root1, root2)])
        while queue:
            node1, node2 = queue.popleft()
            if not node1 or not node2:
                continue
            node1.val += node2.val
            if not node1.left:
                node1.left = node2.left
            else:
                queue.append((node1.left, node2.left))
            if not node1.right:
                node1.right = node2.right
            else:
                queue.append((node1.right, node2.right))
        return root1

Complexity

• Time: O(min(m, n)) where m and n are the number of nodes in the two trees.
• Space: O(min(m, n)) for the queue in the worst case.
• Notes: Modifies root1 in place. Avoids recursion stack overflow on very deep trees.