Merge Two Binary Trees

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.

For example:

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

Input: root1 = [1], root2 = [1,2] Output: [2,2]

How would you approach this problem and implement a solution? Consider edge cases such as empty trees or unbalanced trees. What is the time and space complexity of your solution?

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        # If either tree is empty, return the other tree
        if not root1:
            return root2
        if not root2:
            return root1

        # Create a new node with the sum of the values of the current nodes
        merged_tree = TreeNode(root1.val + root2.val)

        # Recursively merge the left and right subtrees
        merged_tree.left = self.mergeTrees(root1.left, root2.left)
        merged_tree.right = self.mergeTrees(root1.right, root2.right)

        return merged_tree

Naive Approach

The naive approach is to perform a recursive traversal of both trees simultaneously. At each step, if both nodes exist, we add their values and create a new node. If one of the nodes is null, we simply take the other node. This approach directly follows the problem description.

Optimal Approach

The provided solution is already optimal in terms of time complexity. It uses recursion to traverse both trees simultaneously, merging them as it goes.

Big O Runtime Analysis

The time complexity is O(N), where N is the minimum number of nodes in the two trees. In the worst case, we need to visit each node in both trees once.

Big O Space Usage Analysis

The space complexity is O(H), where H is the height of the merged tree. In the worst-case scenario (skewed tree), H can be equal to N, so the space complexity can be O(N). This space is used by the call stack during the recursive calls.

Edge Cases

1. One or both trees are empty: The code handles this case by returning the non-empty tree or None if both are empty.
2. Unbalanced trees: The code correctly merges the trees even if they have different shapes. The recursion continues until both corresponding nodes are None.