Merge Two Binary Trees

Problem Statement

In this programming challenge, you are provided with two binary trees, referred to as root1 and root2. The objective is to merge these two trees into a single binary tree according to specific merging rules. When overlapping the trees, where both trees have a node at the same position, the new tree's corresponding node will have a value equal to the sum of the overlapping nodes' values. In positions where only one tree has a node, the new tree will adopt this non-null node directly. The merging will always begin from the root nodes of both trees. The end result will be a new binary tree representing the accumulated structure and values of the initial trees.

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

Approach and Intuition

Merging two binary trees as described involves recursive or iterative strategies to navigate both trees simultaneously while constructing a new tree. Our approach utilizes a recursive function that tackles one node from each tree at a time. Here's how we can conceptualize the process:

1. Start with the root nodes of both root1 and root2.
2. If both nodes are null, then the merged tree's current node will also be null (base case for recursion).
3. If one node is null, adopt the other non-null node.
4. If both nodes are not null, create a new node for the merged tree with a value equal to the sum of both nodes' values.
5. For non-null pairs of nodes, recursively apply the merge process to their children:
   • Merge the left children of the current nodes to form the left child of the new node.
   • Similarly, merge the right children to form the right child.
6. Continue this process until all nodes in both trees have been visited or merged.

Observations from examples:

• Example 1:
  • The trees root1 = [1,3,2,5] and root2 = [2,1,3,null,4,null,7] when merged, result in [3,4,5,5,4,null,7]. Here, overlapping nodes (e.g., root nodes 1 and 2) sum up to form new nodes (3), and non-overlapping nodes (e.g., the 4 and 7 in root2) are directly adopted.
• Example 2:
  • With root1 = [1] and root2 = [1,2], the result is [2,2] because both trees' root nodes overlap and the additional node in root2 (2) is directly used in the new tree.

This intuitive merging process respects the individual structures of the trees, combining their nodes logically to form a new unified binary tree based on the rules described.

Solutions

public class Solution {
    public TreeNode mergeBinaryTrees(TreeNode tree1, TreeNode tree2) {
        if (tree1 == null)
            return tree2;
        Stack<TreeNode[]> mergeStack = new Stack<>();
        mergeStack.push(new TreeNode[] {tree1, tree2});
        while (!mergeStack.isEmpty()) {
            TreeNode[] nodes = mergeStack.pop();
            if (nodes[0] == null || nodes[1] == null) {
                continue;
            }
            nodes[0].val += nodes[1].val;
            if (nodes[0].left == null) {
                nodes[0].left = nodes[1].left;
            } else {
                mergeStack.push(new TreeNode[] {nodes[0].left, nodes[1].left});
            }
            if (nodes[0].right == null) {
                nodes[0].right = nodes[1].right;
            } else {
                mergeStack.push(new TreeNode[] {nodes[0].right, nodes[1].right});
            }
        }
        return tree1;
    }
}