Domain 1EasyCORE

Merge Two Binary Trees

The problem requires merging two binary trees into one. If nodes overlap in both trees, their values are summed up. Otherwise, the non-null node is used. The merging process starts from the root nodes of both trees.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree

617. Merge Two Binary Trees

Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 75.5%


Problem Breakdown

The problem requires merging two binary trees into one. If nodes overlap in both trees, their values are summed up. Otherwise, the non-null node is used. The merging process starts from the root nodes of both trees.

Inputs:

  • Two binary trees root1 and root2.

Outputs:

  • A new binary tree that is the result of merging root1 and root2.

Implicit Constraints or Edge Cases:

  • If one tree is empty, return the other tree.
  • The number of nodes in both trees ranges from 0 to 2000.
  • Node values range from -10^4 to 10^4.

Intuition

A brute-force approach would involve traversing both trees simultaneously and creating a new tree node for each position, summing the values if they overlap. This approach is straightforward but inefficient in terms of space complexity because it creates a new tree instead of modifying one of the existing trees.

The key insight is to perform an in-place merge by recursively updating nodes from root1 with values from root2. If a node in root1 is null, we can directly use the corresponding node from root2.

Approach

We will use a recursive approach to traverse both trees simultaneously. At each step:

  1. If both nodes are non-null, sum their values and assign it back to root1.
  2. If one of the nodes is null, return the non-null node.
  3. Recursively merge the left children and right children of the current nodes.

This approach modifies root1 in place to save space.

Complexity Analysis

  • Time Complexity: O(n), where n is the total number of nodes in both trees. We visit each node exactly once.
  • Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack. In the worst case, when the tree is skewed, the space complexity can be O(n).

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def mergeTrees(root1: TreeNode, root2: TreeNode) -> TreeNode:
    if not root1:
        return root2
    if not root2:
        return root1
    
    # Sum the values of overlapping nodes
    root1.val += root2.val
    
    # Recursively merge left children
    root1.left = mergeTrees(root1.left, root2.left)
    
    # Recursively merge right children
    root1.right = mergeTrees(root1.right, root2.right)
    
    return root1

Edge Cases Handled

  • Empty Trees: If either root1 or root2 is null, the function returns the other tree.
  • Skewed Trees: The recursive approach handles skewed trees efficiently by only using the height of the tree for the recursion stack.