# LeetCode: 617. Merge Two Binary Trees

**The 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**

```
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]
```

**Solution**

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

```
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (root1 == nullptr) return root2;
if (root2 == nullptr) return root1;
root1->val += root2->val;
root1->left = mergeTrees(root1->left, root2->left);
root1->right = mergeTrees(root1->right, root2->right);
return root1;
}
```

Here's a step-by-step explanation:

- The function
`mergeTrees`

takes two input arguments, which are pointers to the roots of two binary trees (`root1`

and`root2`

). - The first
`if`

condition checks if`root1`

is a nullptr, which means the first tree is empty. If it is, the function returns`root2`

, effectively making the merged tree just the second tree. This covers the case where one tree is empty and the other is not. - The second
`if`

condition checks if`root2`

is a nullptr, which means the second tree is empty. If it is, the function returns`root1`

, since the merged tree should be the first tree in this case. - If both trees are not empty, the values of the nodes in the first tree (
`root1`

) and second tree (`root2`

) are added together. This is done to merge the values of corresponding nodes. - Then, the function recursively calls itself for the left subtrees and right subtrees of both trees. This recursive merging ensures that the structure of the merged tree is correctly maintained.
- Finally, the function returns
`root1`

, which is the merged tree. This tree now contains the updated values and the combined structure of both input trees.