In this post, we are going to solve the 617. Merge Two Binary Trees problem of Leetcode. This problem 617. Merge Two Binary Trees is a Leetcode easy level problem. Let’s see the code, 617. Merge Two Binary Trees – Leetcode Solution.

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 :

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 the tree is in the range [0, 2000].
• -104 <= Node.val <= 104

Now, let’s see the code of 617. Merge Two Binary Trees – Leetcode Solution.

Merge Two Binary Trees – Leetcode Solution

617. Merge Two Binary Trees – Solution in 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 && root2 == null) return null;
        if(root1 == null && root2 !=null) return root2;
        if(root1 != null && root2 == null) return root1;
        
        TreeNode root3 = new TreeNode(root1.val + root2.val);
        
        root3.left = mergeTrees(root1.left,root2.left);
        root3.right = mergeTrees(root1.right,root2.right);
        
        return root3;
    }
}

617. Merge Two Binary Trees – Solution in C++

/**
 * 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* t1, TreeNode* t2) {
        if ( t1 && t2 ) {
            TreeNode * root = new TreeNode(t1->val + t2->val);
            root->left = mergeTrees(t1->left, t2->left);
            root->right = mergeTrees(t1->right, t2->right);
            return root;
        } else {
            return t1 ? t1 : t2;
        }
    }
};

617. Merge Two Binary Trees – Solution in Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def mergeTrees(self, t1, t2):
        if t1 and t2:
            root = TreeNode(t1.val + t2.val)
            root.left = self.mergeTrees(t1.left, t2.left)
            root.right = self.mergeTrees(t1.right, t2.right)
            return root
        else:
            return t1 or t2
        

Note: This problem 617. Merge Two Binary Trees is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.