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:

Input:

    Tree 1                     Tree 2

       1                         2
      / \                       / \
     3   2                     1   3
    /                           \   \
   5                             4   7

Output: Merged tree:

       3
      / \
     4   5
    / \   \
   5   4   7

Solution:

This problem can be solved using recursion. We will create a new tree which will have the sum of the nodes of the two trees.

1. Create a new tree whose root will have the sum of the roots of the two trees.

2. Recursively for the left subtree of the root of the new tree, call mergeTrees function by passing the left child of root1 and the left child of root2.

3. Recursively for the right subtree of the root of the new tree, call mergeTrees function by passing the right child of root1 and the right child of root2.

4. Return the new tree.

Here is the Python code snippet:

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if root1 is None:
            return root2
        if root2 is None:
            return root1
        root1.val += root2.val
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)
        return root1

Time Complexity: O(n), where n is the number of nodes in the bigger tree.

Space Complexity: O(h), where h is the height of the tree. In the worst case, if the trees are skewed, the height can be n, thus space complexity becomes O(n).

1