LeetCode 617: Merge Two Binary Trees

Problem Restatement

We are given two binary trees: root1 and root2.

We need to merge them into a single binary tree.

The merge rule is:

Case	Result
Both nodes exist	Sum their values
One node is null	Use the non-null node
Both null	Result is null

We return the merged tree as the new root.

The official problem defines merging two binary trees by summing overlapping nodes and using the non-null node when only one exists. (leetcode.com)

Input and Output

Function signature:

def mergeTrees(root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
    ...

Input:

Parameter	Meaning
`root1`	First binary tree
`root2`	Second binary tree

Output:

Type	Meaning
`TreeNode`	Root of merged tree

Example

Tree 1:

Tree 2:

Merged tree:

Operation	Result
1 + 2	3
3 + 1	4
2 + 3	5
5	5
4	4
7	7

Result:

First Thought: Modify One Tree

A simple idea is to merge root2 into root1 directly.

If both nodes exist, we update root1.val.

If only one exists, we attach it.

This avoids creating a new tree.

Key Insight

This is a classic DFS tree recursion problem.

At every pair of nodes:

Condition	Action
both nodes exist	merge values
only one exists	return that node
both null	return null

We apply this recursively to left and right children.

Algorithm

For each pair of nodes (n1, n2):

If n1 is null, return n2.
If n2 is null, return n1.
Otherwise:
- Sum values: n1.val += n2.val
- Merge left children
- Merge right children
Return n1 as the merged root.

Implementation

from typing import Optional

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

Code Explanation

We first handle base cases:

if not root1:
    return root2

if not root2:
    return root1

This means:

Case	Meaning
root1 is null	Use root2 directly
root2 is null	Use root1 directly

If both nodes exist, we merge their values:

root1.val += root2.val

Then we recursively merge the left subtree:

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

And the right subtree:

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

Finally, we return the updated root1.

Correctness

The algorithm processes both trees in parallel using DFS.

For each pair of nodes at the same position:

Case	Behavior
both nodes exist	values are added
one node missing	existing subtree is reused
both missing	recursion returns null

Because recursion explores left and right subtrees independently, every node in both trees is visited exactly once.

The merge operation is applied exactly once per overlapping node pair, ensuring correct accumulation of values.

Non-overlapping nodes are preserved without modification.

Therefore, the resulting tree correctly represents the merged structure defined by the problem.

Complexity

Let n be the number of nodes in root1, and m be the number of nodes in root2.

Metric	Value	Why
Time	`O(min(n, m))`	Each overlapping node pair is visited once
Space	`O(h)`	Recursion stack depth equals tree height

Worst case space:

Tree Shape	Space
Balanced	`O(log n)`
Skewed	`O(n)`

Alternative: Create New Tree

We can also build a new tree instead of modifying root1.

class Solution:
    def mergeTrees(
        self,
        root1: Optional[TreeNode],
        root2: Optional[TreeNode]
    ) -> Optional[TreeNode]:

        if not root1 and not root2:
            return None

        val1 = root1.val if root1 else 0
        val2 = root2.val if root2 else 0

        new_root = TreeNode(val1 + val2)

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

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

        return new_root

This version avoids mutating inputs but uses slightly more memory.

Testing

def run_tests():
    s = Solution()

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

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

    merged = s.mergeTrees(t1, t2)

    assert merged.val == 3
    assert merged.left.val == 4
    assert merged.right.val == 5
    assert merged.left.left.val == 5
    assert merged.left.right.val == 4
    assert merged.right.right.val == 7

    t3 = None
    t4 = TreeNode(1)

    assert s.mergeTrees(t3, t4).val == 1

    print("all tests passed")

run_tests()

Test coverage:

Case	Why
Overlapping trees	Confirms value merging
Uneven structure	Confirms subtree reuse
One empty tree	Confirms base case handling