The problem of merging two binary trees involves overlaying one tree onto another. When nodes from both trees overlap, their values are summed to create the value of the new node. If a node exists in only one of the trees, it is directly transferred to the resulting structure. This operation can be efficiently performed using either Depth-First Search (DFS) or Breadth-First Search (BFS).

Depth-First Search Strategy

Recursive traversal is generally preferred for this task due to its conciseness. The algorithm visits nodes starting from the root and proceeds down to the leaves. The merging logic is applied at each step of the recursion.

The core logic hendles three scenarios:

• If both nodes at the current position are null, return null.
• If one node is null, return the non-null node to attach it to the result.
• If both nodes exist, sum their values and recursively process their left and right children.

The following implementation modifies the first tree in place to save space, though creating a new tree is also valid.

/**
 * Definition for a binary tree node.
 */
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 treeA, TreeNode treeB) {
        // If the first node is missing, use the second node
        if (treeA == null) {
            return treeB;
        }
        // If the second node is missing, keep the first node
        if (treeB == null) {
            return treeA;
        }
        
        // Both nodes exist: sum the values
        treeA.val += treeB.val;
        
        // Recursively merge the left and right subtrees
        treeA.left = mergeTrees(treeA.left, treeB.left);
        treeA.right = mergeTrees(treeA.right, treeB.right);
        
        return treeA;
    }
}

Breadth-First Search Strategy

An iterative approach using queues is suitable if avoiding recursion depth limits is a priority. This method processes the trees level by level. It typically involves maintaining separate queues for the result tree and the two input trees to synchronize traversal.

Unlike the recursive solution above, this implementation constructs a complete new tree structure rather than modifying an eixsting one.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public TreeNode mergeTreesIterative(TreeNode rootA, TreeNode rootB) {
        if (rootA == null) return rootB;
        if (rootB == null) return rootA;
        
        // Initialize the root of the merged tree
        TreeNode mergedRoot = new TreeNode(rootA.val + rootB.val);
        
        // Queues to manage traversal for result, tree A, and tree B
        Queue<TreeNode> resultQueue = new LinkedList<>();
        Queue<TreeNode> queueA = new LinkedList<>();
        Queue<TreeNode> queueB = new LinkedList<>();
        
        resultQueue.offer(mergedRoot);
        queueA.offer(rootA);
        queueB.offer(rootB);
        
        while (!queueA.isEmpty() && !queueB.isEmpty()) {
            TreeNode current = resultQueue.poll();
            TreeNode nodeA = queueA.poll();
            TreeNode nodeB = queueB.poll();
            
            // Handle left children
            TreeNode leftChildA = nodeA.left;
            TreeNode leftChildB = nodeB.left;
            
            if (leftChildA != null || leftChildB != null) {
                if (leftChildA != null && leftChildB != null) {
                    TreeNode newLeft = new TreeNode(leftChildA.val + leftChildB.val);
                    current.left = newLeft;
                    resultQueue.offer(newLeft);
                    queueA.offer(leftChildA);
                    queueB.offer(leftChildB);
                } else if (leftChildA != null) {
                    current.left = leftChildA;
                } else {
                    current.left = leftChildB;
                }
            }
            
            // Handle right children
            TreeNode rightChildA = nodeA.right;
            TreeNode rightChildB = nodeB.right;
            
            if (rightChildA != null || rightChildB != null) {
                if (rightChildA != null && rightChildB != null) {
                    TreeNode newRight = new TreeNode(rightChildA.val + rightChildB.val);
                    current.right = newRight;
                    resultQueue.offer(newRight);
                    queueA.offer(rightChildA);
                    queueB.offer(rightChildB);
                } else if (rightChildA != null) {
                    current.right = rightChildA;
                } else {
                    current.right = rightChildB;
                }
            }
        }
        
        return mergedRoot;
    }
}