{x}
blog image

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.

 

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

Solution Explanation

This problem involves merging two binary trees. The merging rule is straightforward: if two nodes overlap (i.e., both exist at the same position in the tree), their values are summed to form the new node's value. Otherwise, the node that exists becomes the node in the merged tree.

The most efficient way to solve this is using recursion. We recursively traverse both trees simultaneously.

Approach:

  1. Base Cases:

    • If root1 is null, return root2.
    • If root2 is null, return root1. This handles cases where one tree is empty or a subtree is empty.

  2. Recursive Step:

    • Create a new node with the sum of the values from root1 and root2.
    • Recursively call mergeTrees on the left subtrees (root1.left, root2.left) and the right subtrees (root1.right, root2.right). Assign the results to the left and right children of the newly created node.
    • Return the newly created node.

Code Explanation (Python Example):

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 is None:
            return root2
        if root2 is None:
            return root1
        node = TreeNode(root1.val + root2.val) # Create new node with summed value
        node.left = self.mergeTrees(root1.left, root2.left) # Recursively merge left subtrees
        node.right = self.mergeTrees(root1.right, root2.right) # Recursively merge right subtrees
        return node

The code in other languages follows the same recursive logic, differing only in syntax.

Time Complexity Analysis:

The time complexity is O(N), where N is the number of nodes in the smaller of the two trees. In the worst case, we visit each node in the smaller tree once. The larger tree's nodes that don't have corresponding nodes in the smaller tree will also be visited once. The number of operations is proportional to the size of the smaller tree.

Space Complexity Analysis:

The space complexity is O(H), where H is the height of the taller of the two trees. This space is used by the recursive call stack. In the worst case (a skewed tree), H could be equal to N (the number of nodes). In the best case (a balanced tree), H would be log₂(N). Therefore we can generally express it as O(min(H1,H2)), where H1 and H2 are the heights of the trees.