Merge Binary Trees

Tags

Merge Binary Trees

Category

Binary Trees

Difficulty

Medium

Problem Statement

Given two binary trees, merge them into a single binary tree. When two nodes overlap (occupy the same position), sum their values. If only one tree has a node at a given position, use that node in the merged tree. Return the root of the merged tree.

Intuition

We can traverse both trees simultaneously. At each position, if both trees have a node, we create a merged node with the sum of values and recursively merge their children. If only one tree has a node, we use that subtree directly. This is a natural recursive traversal where we process corresponding nodes in parallel.

Approach

  1. If both nodes are null, return null.
  2. If one node is null, return the other node (its entire subtree becomes part of the merged tree).
  3. If both nodes exist: a. Create a new node (or modify one of the existing nodes) with value = node1.value + node2.value. b. Recursively merge the left children of both nodes. c. Recursively merge the right children of both nodes.
  4. Return the merged node.

Pseudocode

function mergeBinaryTrees(tree1, tree2):
    if tree1 is null: return tree2
    if tree2 is null: return tree1

    // Mutate tree1 in-place (or create new node)
    tree1.value += tree2.value
    tree1.left = mergeBinaryTrees(tree1.left, tree2.left)
    tree1.right = mergeBinaryTrees(tree1.right, tree2.right)
    return tree1

Time & Space Complexity

  • Time: O(min(n1, n2)) where n1 and n2 are the number of nodes in each tree. We visit each overlapping position once, and the recursion short-circuits when one subtree is null.
  • Space: O(min(h1, h2)) for the recursion stack, where h1 and h2 are the heights of the trees. In the worst case, O(min(n1, n2)) for skewed trees.

Key Insights

  • The merge can be done in-place by modifying one of the input trees, avoiding the creation of new nodes.
  • When one subtree is null, we can directly attach the other subtree without traversing it further.
  • An iterative approach using a stack or queue is also possible, processing pairs of corresponding nodes.
  • The merged tree's structure is the union of both input tree structures.

Edge Cases

  • Both trees are null: return null.
  • One tree is null: return the other tree unchanged.
  • Trees with completely different structures (no overlapping positions): the merged tree is a combination of both shapes.
  • Trees with identical structures: every node is summed.
  • Single-node trees: return a node with the sum of both values.

Linked mentions