We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Merge Two Binary Trees

Number: 617

Difficulty: Easy

Paid? No

Companies: Amazon, Meta, MongoDB, Yahoo

Problem Description

Merge two binary trees by overlaying them. When two nodes overlap, sum their values. If one node is missing, use the existing node from the other tree. The merging process starts at the root nodes of both trees.

Key Insights

  • Use recursion to traverse both trees simultaneously.
  • When both nodes are non-null, add their values and recursively merge their left and right children.
  • If one of the nodes is null, return the other non-null node directly.
  • The new tree is built by updating one of the input trees in place with the merged result.

Space and Time Complexity

Time Complexity: In the worst-case scenario when both trees have the same structure, the algorithm visits every node, resulting in O(n) time, where n is the total number of nodes in the merged tree. Space Complexity: O(max(h1, h2)) due to recursion stack space, where h1 and h2 are the heights of the trees. In the worst-case (skewed trees), this becomes O(n).

Solution

The solution uses a recursive DFS (Depth-First Search) approach to merge the two trees:

  1. If one of the current nodes is null, return the other node immediately.
  2. If both nodes exist, add the value of the second node to the first node.
  3. Recursively merge the left children and then the right children.
  4. Return the modified first tree, which represents the merged tree. This approach leverages the call stack for recursion and modifies one of the trees directly to obtain the merged result.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val        # Node value
        self.left = left      # Left child reference
        self.right = right    # Right child reference

def mergeTrees(root1, root2):
    # If the first tree is None, return the second tree.
    if not root1:
        return root2
    # If the second tree is None, return the first tree.
    if not root2:
        return root1
    # Add the values of overlapping nodes.
    root1.val += root2.val
    # Recursively merge the left children.
    root1.left = mergeTrees(root1.left, root2.left)
    # Recursively merge the right children.
    root1.right = mergeTrees(root1.right, root2.right)
    # Return the merged tree rooted at root1.
    return root1
← Back to All Questions