617. Merge Two Binary Trees - Explanation

Description

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 = [2]

Output: [3]

Example 3:

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

Output: [2]

Constraints:

0 <= The number of nodes in both the trees <= 2000.
-10,000 <= Node.val <= 10,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Depth First Search (Creating New Tree)

# 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 not root1 and not root2:
            return None

        v1 = root1.val if root1 else 0
        v2 = root2.val if root2 else 0
        root = TreeNode(v1 + v2)

        root.left = self.mergeTrees(root1.left if root1 else None, root2.left if root2 else None)
        root.right = self.mergeTrees(root1.right if root1 else None, root2.right if root2 else None)

        return root

Time & Space Complexity

Time complexity: $O(m + n)$
Space complexity:
- $O(m + n)$ space for recursion stack.
- $O(m + n)$ space for the output.

Where $m$ and $n$ are the number of nodes in the given trees.

2. Depth First Search (In Place)

# 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 not root1:
            return root2
        if not root2:
            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 & Space Complexity

Time complexity: $O(min(m, n))$
Space complexity: $O(min(m, n))$ for recursion stack.

Where $m$ and $n$ are the number of nodes in the given trees.

3. Iterative DFS (Creating New Tree)

# 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 not root1:
            return root2
        if not root2:
            return root1

        root = TreeNode(root1.val + root2.val)
        stack = [(root1, root2, root)]

        while stack:
            node1, node2, node = stack.pop()

            if node1.left and node2.left:
                node.left = TreeNode(node1.left.val + node2.left.val)
                stack.append((node1.left, node2.left, node.left))
            elif not node1.left:
                node.left = node2.left
            else:
                node.left = node1.left

            if node1.right and node2.right:
                node.right = TreeNode(node1.right.val + node2.right.val)
                stack.append((node1.right, node2.right, node.right))
            elif not node1.right:
                node.right = node2.right
            else:
                node.right = node1.right

        return root

Time & Space Complexity

Time complexity: $O(m + n)$
Space complexity:
- $O(m + n)$ space for the stack.
- $O(m + n)$ space for the output.

Where $m$ and $n$ are the number of nodes in the given trees.

4. Iterative DFS (In Place)

# 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 not root1:
            return root2
        if not root2:
            return root1

        stack = [(root1, root2)]

        while stack:
            node1, node2 = stack.pop()
            if not node1 or not node2:
                continue

            node1.val += node2.val

            if node1.left and node2.left:
                stack.append((node1.left, node2.left))
            elif not node1.left:
                node1.left = node2.left

            if node1.right and node2.right:
                stack.append((node1.right, node2.right))
            elif not node1.right:
                node1.right = node2.right

        return root1

Time & Space Complexity

Time complexity: $O(min(m, n))$
Space complexity: $O(min(m, n))$ for the stack.

Where $m$ and $n$ are the number of nodes in the given trees.