Merge Two Binary Trees

Easy · Graphs · Explanation and code example

Iterative DFS (In Place)

How it works

Similar to the recursive in-place approach, we can modify the first tree iteratively using a stack. We push pairs of nodes from both trees. When both nodes exist, we add values and continue processing children. If only one tree has a child at a position, we directly attach that subtree to the first tree. This avoids creating new nodes.

Steps

  1. Handle base cases where one or both trees are null.
  2. Initialize a stack with the pair (root1, root2).
  3. While the stack is not empty:
    • Pop (node1, node2). Skip if either is null.
    • Add node2.val to node1.val.
    • If both have left children, push them to the stack. Otherwise, if node1 has no left child, attach node2.left.
    • Similarly handle right children.
  4. Return root1.

Complexity

  • Time complexity: O(min(m, n))
  • Space complexity: O(min(m, n)) for the stack.

Where m and n are the number of nodes in the given trees.

Things to watch for

Not Handling the Case When One Tree is Null

When one of the input trees is null at a position while the other is not, you should return the non-null subtree directly. Failing to handle this base case properly leads to null pointer exceptions or missing nodes in the result.

Modifying the Input Trees Unintentionally

When using the in-place approach, the first tree is modified to become the merged result. If the original trees need to be preserved for other purposes, this causes unexpected side effects. Use the approach that creates a new tree if the inputs must remain unchanged.

Python code example

from typing import Optional

# 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 not root1:
            return root2
        if not root2:
            return root1

        stack = [(root1, root2)]

        while stack:
            node1, node2 = stack.pop()
            if not node1 or not node2:
                continue

            node1.val += node2.val

            if node1.left and node2.left:
                stack.append((node1.left, node2.left))
            elif not node1.left:
                node1.left = node2.left

            if node1.right and node2.right:
                stack.append((node1.right, node2.right))
            elif not node1.right:
                node1.right = node2.right

        return root1

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (!root1) return root2;
        if (!root2) return root1;

        stack<pair<TreeNode*, TreeNode*>> stk;
        stk.push({root1, root2});

        while (!stk.empty()) {
            auto [node1, node2] = stk.top();
            stk.pop();

            if (!node2) continue;

            node1->val += node2->val;

            if (!node1->left) {
                node1->left = node2->left;
            } else {
                stk.push({node1->left, node2->left});
            }

            if (!node1->right) {
                node1->right = node2->right;
            } else {
                stk.push({node1->right, node2->right});
            }
        }

        return root1;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations