# Merge Two Binary Trees
**Difficulty:** EASY
[External](https://leetcode.com/problems/merge-two-binary-trees)
Canonical: https://scaleengineer.com/dsa/problems/merge-two-binary-trees
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [MongoDB](https://scaleengineer.com/companies/mongodb)
---
## Problem
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:**

![](https://assets.glich.co/dsa/merge-two-binary-trees/image0.jpg) 

**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
## Recursive Approach (Creating a New Tree)
This approach involves creating a completely new binary tree to store the merged result. A recursive function traverses both trees simultaneously. For each pair of corresponding nodes, it creates a new node in the result tree based on the merge rule. This method is conceptually simple but has a higher space cost.
**Time:** O(N), where N is the total number of nodes in the final merged tree. We need to visit every node that will be part of the new tree to create it. · **Space:** O(N), where N is the total number of nodes in the final merged tree. This is because we are creating a new tree of size N. The recursion stack also uses space, up to O(H) where H is the maximum height of the trees, but this is dominated by the O(N) space for the new tree itself.
**Pros:** It does not modify the original input trees, which can be a desirable property.; The logic is straightforward and easy to understand.
**Cons:** Uses significant extra space to create an entirely new tree, making it the least space-efficient solution.
### Explanation
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.

```java
/**
 * 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;
        }
        // Both nodes are non-null, create a new node with the sum
        TreeNode mergedNode = new TreeNode(root1.val + root2.val);
        // Recursively merge the left and right subtrees
        mergedNode.left = mergeTrees(root1.left, root2.left);
        mergedNode.right = mergeTrees(root1.right, root2.right);
        return mergedNode;
    }
}
```
### Algorithm
- 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)`.

## Iterative Approach (In-place Modification)
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.
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Recursive Approach (In-place Modification)
This is the most common and often most efficient approach. It uses recursion to traverse the trees, but instead of creating new nodes, it modifies one of the existing trees (e.g., `tree1`) to become the merged tree. This significantly reduces space consumption while maintaining clean, readable code.
**Time:** O(M), where M is the number of nodes in the smaller of the two trees (or more accurately, the number of overlapping nodes). We only make recursive calls for overlapping nodes. · **Space:** O(H), where H is the maximum height of the two trees. This space is used by the recursion call stack. For a balanced tree, this is O(log N), and for a skewed tree, it's O(N).
**Pros:** Very space-efficient as it doesn't create a new tree.; The code is concise, elegant, and highly readable.; Often has the best average-case space complexity (O(log N) for balanced trees).
**Cons:** It modifies one of the original input trees.; Can lead to a stack overflow error if the trees are extremely deep and skewed, though this is rare under typical constraints.
### Explanation
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`.

```java
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }

        // Both nodes exist, merge t2 into t1
        t1.val += t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);

        return t1;
    }
}
```
### Algorithm
- 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)`.

# Solutions
### Java

```java
/** * 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 ; } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root1 * @param {TreeNode} root2 * @return {TreeNode} */ var mergeTrees =
  function (root1, root2) {
    if (!root1) {
      return root2;
    }
    if (!root2) {
      return root1;
    }
    const node = new TreeNode(root1.val + root2.val);
    node.left = mergeTrees(root1.left, root2.left);
    node.right = mergeTrees(root1.right, root2.right);
    return node;
  };

```

### CPP

```cpp
/** * 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 ; TreeNode * node = new TreeNode ( root1 -> val + root2 -> val ); node -> left = mergeTrees ( root1 -> left , root2 -> left ); node -> right = mergeTrees ( root1 -> right , root2 -> right ); return node ; } };
```

### Python

```python
# 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 root1 is None : return root2 if root2 is None : return root1 node = TreeNode ( root1 . val + root2 . val ) node . left = self . mergeTrees ( root1 . left , root2 . left ) node . right = self . mergeTrees ( root1 . right , root2 . right ) return node
```