Scale Engineer

Merge Two Binary Trees

Easy
#0576Time: 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: 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).1 company
Algorithms
Depth-First SearchBreadth-First Search
Data structures
TreeBinary Tree
Companies
MongoDB

Prompt

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].
  • -104 <= Node.val <= 104

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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).

Trade-offs

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.

Solutions

/** * 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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem