Merge Two Binary Trees

EASY

Description

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.

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⁴

Approaches

Checkout 3 different approaches to solve Merge Two Binary Trees. Click on different approaches to view the approach and algorithm in detail.

Iterative Approach (In-place Modification)

This approach avoids recursion by using a stack to perform a pre-order traversal of the trees. It modifies one of the trees (e.g., tree1) in-place to store the merged result, which saves space compared to creating a new tree. This is useful for avoiding stack overflow on extremely deep trees.

Algorithm

If root1 is null, return root2.
Create a Stack and push a TreeNode[] pair containing [root1, root2].
Loop while the stack is not empty:
- Pop the pair [t1, t2].
- If t2 is null, continue to the next iteration.
- Add t2.val to t1.val.
- For the left children: If t1.left is null, set t1.left = t2.left. Otherwise, push [t1.left, t2.left] to the stack.
- For the right children: If t1.right is null, set t1.right = t2.right. Otherwise, push [t1.right, t2.right] to the stack.
Return root1.

The core idea is to use a stack to keep track of pairs of nodes from tree1 and tree2 that need to be processed. We will merge tree2 into tree1.

First, handle the edge case where one of the root nodes is null. If root1 is null, we can simply return root2.
Push the root pair [root1, root2] onto the stack.
While the stack is not empty, pop a pair [t1, t2].
If t2 is null, there's nothing to merge for this pair, so we continue.
Sum the values: t1.val += t2.val.
Now, consider the left children. If t1 has a left child, we need to check t2's left child. If t2 also has a left child, we push the pair [t1.left, t2.left] to the stack for future processing. If t1 does not have a left child but t2 does, we can directly attach t2's left subtree to t1 by setting t1.left = t2.left.
The same logic is applied to the right children.
After the loop finishes, root1 will be the root of the merged tree.

import java.util.Stack;

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        // We will merge root2 into root1
        Stack<TreeNode[]> stack = new Stack<>();
        stack.push(new TreeNode[]{root1, root2});

        while (!stack.isEmpty()) {
            TreeNode[] t = stack.pop();
            // No need to merge if t[1] is null, as t[0] remains as is.
            if (t[0] == null || t[1] == null) {
                continue;
            }

            // Add t[1]'s value to t[0]'s
            t[0].val += t[1].val;

            // Process left children
            if (t[0].left == null) {
                t[0].left = t[1].left;
            } else {
                stack.push(new TreeNode[]{t[0].left, t[1].left});
            }

            // Process right children
            if (t[0].right == null) {
                t[0].right = t[1].right;
            } else {
                stack.push(new TreeNode[]{t[0].right, t[1].right});
            }
        }
        return root1;
    }
}

Complexity Analysis

Time Complexity: O(M), where M is the number of overlapping nodes in the two trees. We only push pairs to the stack where both nodes exist, so we only iterate over the overlapping parts.Space Complexity: O(W), where W is the maximum width of the trees. In the worst case of a complete binary tree, the width can be O(N), where N is the number of nodes. In the best case of a skewed tree, the space is O(1).

Pros and Cons

Pros:

Avoids recursion, preventing potential stack overflow errors for very deep trees.
More space-efficient than creating a new tree since it modifies one in-place.

Cons:

Modifies one of the original input trees.
The code can be slightly more complex to write and understand compared to the recursive version.
Worst-case space complexity for the stack can be O(N) for wide, bushy trees.

Code Solutions

Checking out 4 solutions in different languages for Merge Two Binary Trees. Click on different languages to view the code.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode mergeTrees ( TreeNode root1 , TreeNode root2 ) { if ( root1 == null ) { return root2 ; } if ( root2 == null ) { return root1 ; } TreeNode node = new TreeNode ( root1 . val + root2 . val ); node . left = mergeTrees ( root1 . left , root2 . left ); node . right = mergeTrees ( root1 . right , root2 . right ); return node ; } }

Video Solution

Watch the video walkthrough for Merge Two Binary Trees

Algorithms:

Depth-First SearchBreadth-First Search

Data Structures:

TreeBinary Tree

Companies:

MongoDB |