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:

1. The function mergeTrees takes two input arguments, which are pointers to the roots of two binary trees (root1 and root2).
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.