Merge Two Binary Trees

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

1import java.util.Stack;2 3class Solution {4    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {5        if (root1 == null) {6            return root2;7        }8        // We will merge root2 into root19        Stack<TreeNode[]> stack = new Stack<>();10        stack.push(new TreeNode[]{root1, root2});11 12        while (!stack.isEmpty()) {13            TreeNode[] t = stack.pop();14            // No need to merge if t[1] is null, as t[0] remains as is.15            if (t[0] == null || t[1] == null) {16                continue;17            }18 19            // Add t[1]'s value to t[0]'s20            t[0].val += t[1].val;21 22            // Process left children23            if (t[0].left == null) {24                t[0].left = t[1].left;25            } else {26                stack.push(new TreeNode[]{t[0].left, t[1].left});27            }28 29            // Process right children30            if (t[0].right == null) {31                t[0].right = t[1].right;32            } else {33                stack.push(new TreeNode[]{t[0].right, t[1].right});34            }35        }36        return root1;37    }38}

• Define a recursive function merge(node1, node2) that returns a new TreeNode.
• Base Case 1: If node1 is null, return node2.
• Base Case 2: If node2 is null, return node1.
• Recursive Step: If both nodes are non-null:
  • Create a new TreeNode with a value of node1.val + node2.val.
  • Set the new node's left child to the result of merge(node1.left, node2.left).
  • Set the new node's right child to the result of merge(node1.right, node2.right).
  • Return the new node.
• The initial call is merge(root1, root2).

We define a recursive helper function, say merge(node1, node2). The function's logic is as follows:

• Base Cases:

  • If node1 is null, it means there's no corresponding node in the first tree. We simply return node2 (which could be a subtree or null), as it will be the node in the merged tree.
  • Similarly, if node2 is null, we return node1.

• Recursive Step:

  • If both node1 and node2 are non-null, they overlap. We create a new TreeNode whose value is the sum of node1.val and node2.val.
  • The left child of this new node is determined by a recursive call: newNode.left = merge(node1.left, node2.left).
  • The right child is determined similarly: newNode.right = merge(node1.right, node2.right).
  • The newly created node is then returned.

The initial call to this function will be merge(root1, root2), which will build and return the root of the new merged tree.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {18        if (root1 == null) {19            return root2;20        }21        if (root2 == null) {22            return root1;23        }24        // Both nodes are non-null, create a new node with the sum25        TreeNode mergedNode = new TreeNode(root1.val + root2.val);26        // Recursively merge the left and right subtrees27        mergedNode.left = mergeTrees(root1.left, root2.left);28        mergedNode.right = mergeTrees(root1.right, root2.right);29        return mergedNode;30    }31}

• Define a recursive function merge(t1, t2) that returns the merged TreeNode.
• Base Case 1: If t1 is null, return t2.
• Base Case 2: If t2 is null, return t1.
• Recursive Step: If both nodes are non-null:
  • Update t1.val by adding t2.val to it.
  • Recursively call merge(t1.left, t2.left) and assign the result to t1.left.
  • Recursively call merge(t1.right, t2.right) and assign the result to t1.right.
  • Return the modified t1 node.
• The initial call is merge(root1, root2).

The function mergeTrees(t1, t2) returns the merged tree node by modifying t1 in-place.

• Base Cases:

  • If t1 is null, it means there's no node in the first tree at this position. The result of the merge is simply the subtree from the second tree, so we return t2. This effectively attaches t2's subtree to the parent in the first tree.
  • If t2 is null, there's nothing to merge from the second tree. We can just return the existing node t1 as is.

• Recursive Step:

  • If both t1 and t2 are non-null, we are at an overlapping node. We update the value of t1 by adding t2.val to it: t1.val += t2.val.
  • We then recursively merge the left subtrees and update t1's left child with the result: t1.left = mergeTrees(t1.left, t2.left).
  • Similarly, we merge the right subtrees: t1.right = mergeTrees(t1.right, t2.right).
  • Finally, we return the modified t1 node.

The initial call mergeTrees(root1, root2) will return the root of the fully merged tree, which is the modified root1.

1class Solution {2    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {3        if (t1 == null) {4            return t2;5        }6        if (t2 == null) {7            return t1;8        }9 10        // Both nodes exist, merge t2 into t111        t1.val += t2.val;12        t1.left = mergeTrees(t1.left, t2.left);13        t1.right = mergeTrees(t1.right, t2.right);14 15        return t1;16    }17}