LeetCode 617 - Merge Two Binary Trees

This problem asks us to combine two binary trees into a single merged tree. Each tree consists of nodes where every node contains a value and pointers to a left and right child.

leetcodeeasytreedepth-first-searchbreadth-first-searchbinary-tree

LeetCode Problem 617

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to combine two binary trees into a single merged tree. Each tree consists of nodes where every node contains a value and pointers to a left and right child.

The merge process starts from the roots of both trees and proceeds recursively through corresponding positions in the trees. Whenever both trees contain a node at the same position, their values are added together to create the merged node's value. If only one tree contains a node at a position and the other tree has null, then the existing node is used directly in the merged tree.

For example, suppose the first tree has a node with value 3 at a particular position and the second tree also has a node with value 5 at that same position. The merged tree will contain a node with value 8 there. If only one tree contains a node, that node remains unchanged in the merged result.

The input is given as two binary tree roots, root1 and root2. Each root may be null, which represents an empty tree. The output must be the root of the merged binary tree.

The constraints tell us that the total number of nodes across both trees is at most 2000. This is small enough that traversing every node is completely acceptable. Since the problem naturally involves recursively comparing corresponding nodes, a depth first traversal is a very natural fit.

Several edge cases are important:

  • One or both trees may be empty.
  • Trees may have very different shapes.
  • A node may exist in one tree but not the other.
  • Node values may be negative.
  • Trees may be highly unbalanced, creating deep recursion paths.

The problem guarantees valid binary tree inputs, so we do not need to validate tree structure correctness.

Approaches

Brute Force Approach

A brute force approach would first copy both trees into auxiliary data structures such as arrays or hash maps keyed by traversal position. After converting both trees into comparable representations, we could iterate through all positions, sum overlapping values, and rebuild an entirely new tree.

This works because every node position can eventually be compared explicitly. However, it introduces unnecessary overhead. Binary trees are already recursive structures, so flattening them into another representation wastes both time and memory.

Additionally, reconstructing the tree afterward complicates the implementation significantly. The problem can instead be solved directly during traversal.

Optimal Approach

The key observation is that merging can happen naturally during a recursive traversal.

At every pair of nodes:

  • If both nodes are null, the merged node is also null.
  • If one node is null, return the other node directly.
  • If both nodes exist, create or update a node whose value is the sum of the two node values.
  • Recursively merge the left children.
  • Recursively merge the right children.

Because each node pair is processed exactly once, this solution is both simple and efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n + m) O(n + m) Converts trees into auxiliary structures before rebuilding
Optimal O(n + m) O(h) Recursively merges nodes directly during traversal

Here, n and m are the number of nodes in the two trees, and h is the height of the recursion stack.

Algorithm Walkthrough

  1. Start at the root nodes of both trees.

We compare the roots because the merge process always begins from the top of both trees. 2. Check whether both nodes are null.

If both nodes are empty, there is nothing to merge, so return null. 3. Check whether one node is null.

If one tree does not contain a node at this position, return the existing node from the other tree directly. This preserves the subtree structure. 4. Merge the current node values.

If both nodes exist, add their values together. We can reuse one of the existing nodes instead of allocating a completely new node. 5. Recursively merge the left subtrees.

Call the merge function on root1.left and root2.left. Assign the returned node to the merged node's left child. 6. Recursively merge the right subtrees.

Call the merge function on root1.right and root2.right. Assign the returned node to the merged node's right child. 7. Return the merged node.

After both children are processed, the current subtree is fully merged.

Why it works

The algorithm works because each recursive call correctly merges the corresponding pair of nodes from the two trees. The recursion preserves the relative structure of the trees while applying the merge rule locally at every node. Since every subtree is merged correctly before returning upward, the entire final tree is guaranteed to be correct.

Python Solution

# 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

from typing import Optional

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

        root1.val += root2.val

        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)

        return root1

The implementation follows the recursive strategy directly.

The first two condition checks handle the cases where one of the trees is empty at the current position. Returning the non-null node immediately avoids unnecessary work and preserves the existing subtree structure.

When both nodes exist, the current node values are added together. The implementation reuses root1 as the merged node to reduce memory usage.

The recursive calls merge the left and right children independently. Each recursive call returns the root of the merged subtree, which is assigned back to root1.left and root1.right.

Finally, the merged node is returned upward through the recursion chain.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil {
        return root2
    }

    if root2 == nil {
        return root1
    }

    root1.Val += root2.Val

    root1.Left = mergeTrees(root1.Left, root2.Left)
    root1.Right = mergeTrees(root1.Right, root2.Right)

    return root1
}

The Go implementation is almost identical to the Python version conceptually.

Go uses nil instead of None for empty pointers. Tree nodes are manipulated through pointers, so modifying root1.Val directly updates the existing node.

Since Go integers comfortably handle the given value constraints, integer overflow is not a concern here.

Worked Examples

Example 1

Input:

root1 = [1,3,2,5]
root2 = [2,1,3,null,4,null,7]

Tree structures:

Tree 1:              Tree 2:

     1                    2
    / \                  / \
   3   2                1   3
  /                      \    \
 5                        4    7

Step by step traversal:

Current Nodes Action Result Node
1 and 2 Sum values 3
3 and 1 Sum values 4
5 and null Keep existing node 5
null and 4 Keep existing node 4
2 and 3 Sum values 5
null and 7 Keep existing node 7

Merged tree:

        3
       / \
      4   5
     / \   \
    5   4   7

Output:

[3,4,5,5,4,null,7]

Example 2

Input:

root1 = [1]
root2 = [1,2]

Tree structures:

Tree 1:        Tree 2:

   1              1
                 /
                2

Step by step traversal:

Current Nodes Action Result
1 and 1 Sum values 2
null and 2 Keep existing node 2

Merged tree:

    2
   /
  2

Output:

[2,2]

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Every node from both trees is visited at most once
Space O(h) Recursive call stack depth equals tree height

The time complexity is linear because each node participates in exactly one merge operation. No node is revisited.

The space complexity comes from recursion. In the worst case of a completely skewed tree, the recursion depth may reach O(n + m). For balanced trees, the recursion depth is closer to O(log(n + m)).

Test Cases

# Helper functions for testing

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

def tree_to_list(root):
    if not root:
        return []

    result = []
    queue = [root]

    while queue:
        node = queue.pop(0)

        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)

    while result and result[-1] is None:
        result.pop()

    return result

s = Solution()

# Example 1
t1 = TreeNode(1,
    TreeNode(3, TreeNode(5)),
    TreeNode(2)
)

t2 = TreeNode(2,
    TreeNode(1, None, TreeNode(4)),
    TreeNode(3, None, TreeNode(7))
)

assert tree_to_list(s.mergeTrees(t1, t2)) == [3, 4, 5, 5, 4, None, 7]  # standard merge case

# Example 2
t1 = TreeNode(1)
t2 = TreeNode(1, TreeNode(2))

assert tree_to_list(s.mergeTrees(t1, t2)) == [2, 2]  # one-sided subtree

# Both trees empty
assert s.mergeTrees(None, None) is None  # empty input trees

# First tree empty
t2 = TreeNode(5)
assert tree_to_list(s.mergeTrees(None, t2)) == [5]  # return second tree directly

# Second tree empty
t1 = TreeNode(8)
assert tree_to_list(s.mergeTrees(t1, None)) == [8]  # return first tree directly

# Trees with negative values
t1 = TreeNode(-1, TreeNode(-2))
t2 = TreeNode(3, TreeNode(4))

assert tree_to_list(s.mergeTrees(t1, t2)) == [2, 2]  # negative and positive values

# Uneven tree shapes
t1 = TreeNode(1, TreeNode(2, TreeNode(3)))
t2 = TreeNode(4)

assert tree_to_list(s.mergeTrees(t1, t2)) == [5, 2, None, 3]  # deep left subtree preserved

# Deep right subtree
t1 = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
t2 = TreeNode(1)

assert tree_to_list(s.mergeTrees(t1, t2)) == [2, None, 2, None, 3]  # right-heavy structure
Test Why
Standard overlapping trees Validates normal merge behavior
One-sided subtree Ensures missing nodes are preserved
Both trees empty Confirms null handling
First tree empty Ensures second tree is returned correctly
Second tree empty Ensures first tree is returned correctly
Negative values Verifies summation with negative numbers
Uneven shapes Confirms structural preservation
Deep right subtree Tests recursion on skewed trees

Edge Cases

Both Trees Are Empty

If both root1 and root2 are null, the algorithm should return null. This case is important because recursive solutions can accidentally dereference null pointers if base conditions are not checked first. The implementation handles this immediately through the initial null checks.

One Tree Is Much Larger Than the Other

One tree may contain many nodes while the other tree contains only a few. A buggy implementation might incorrectly discard unmatched subtrees. This solution correctly preserves all unmatched nodes because whenever one node is null, the algorithm returns the non-null subtree directly.

Highly Skewed Trees

A tree may resemble a linked list rather than a balanced tree. This creates deep recursive chains and tests whether the recursion logic correctly processes one child at a time. The implementation works correctly because every recursive call independently merges corresponding left and right children, regardless of tree balance.

Negative Node Values

The node values can be negative, so the merge operation cannot assume positive sums. The implementation simply performs integer addition without imposing constraints on sign, making it naturally compatible with negative values.