Merge Two Binary Trees LeetCode Solution

Problem Statement

Merge Two Binary Trees LeetCode Solution – 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.

Example

Test Case 1:

Input:

root1 = [1, 3, 2, 5]

root2 = [2, 1, 3, null, 4, null, 7]

Output:

[3, 4, 5,  5, 6, null, 7]

Explanation

After merging the Binary trees the output tree becomes [3, 4, 5,  5, 6, null, 7].

Approach

Idea

We can traverse both the given trees in a preorder fashion. At every step, we check if the current node exists(isn’t null) for both the trees. If so, we add the values in the current nodes of both the trees and update the value in the current node of the first tree to reflect this sum obtained. At every step, we also call the original function mergeTrees() with the left children and then with the right children of the current nodes of the two trees. If at any step, one of these children happens to be null, we return the child of the other tree(representing the corresponding child subtree) to be added as a child subtree to the calling parent node in the first tree. At the end, the first tree will represent the required resultant merged binary tree.

Code for Merge Two Binary Trees LeetCode Solution

Java Program

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;
    }
}

C++ Program

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (!root1 || !root2) return root1 ? root1 : root2;

        TreeNode* node = new TreeNode(root1->val + root2->val);
        node->left = mergeTrees(root1->left, root2->left);
        node->right = mergeTrees(root1->right, root2->right);
        return node;
    }
};

Complexity Analysis for Merge Two Binary Trees LeetCode Solution

Time Complexity will be $O(m)$. A total of m nodes need to be traversed. Here, m represents the minimum number of nodes from the two given trees.

Space Complexity will be $O(m)$. The depth of the recursion tree can go up to m in the case of a skewed tree. In an average case, depth will be O(logm).

Reference: https://en.wikipedia.org/?title=Pre-order_traversal