Merge Two Binary Trees

Easy
1876.

Merge Two Binary Trees

Merge Two Binary Trees is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Microsoft and Adobe interviews.

You are given the roots root1 and root2 of two binary trees. Imagine laying one over the other, root on root. Merge them into one tree: where both trees have a node in the same position, the merged node's value is the sum of the two; where only one tree has a node, that node (with its whole subtree) is used as it is.

Return the root of the merged tree. Merging starts at the roots.

Example 1

Input
root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output
[3,4,5,5,4,null,7]
Explanation
Overlapping positions add up (1+2, 3+1, 2+3); 5 exists only in the first tree, 4 and 7 only in the second.

Example 2

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

Example 3

Input
root1 = [], root2 = [4,null,-6]
Output
[4,null,-6]
Explanation
With one tree empty, the merge is just the other tree.

Constraints

  • The number of nodes in both trees is in the range [0, 2000]
  • -10^4 <= Node.val <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {TreeNode}
 */
var mergeTrees = function(root1, root2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Merge Two Binary Trees — Solution in Python, Java & C++

Merge Two Binary Trees solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Merge Two Binary Trees is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Microsoft and Adobe interviews.

Problem statement

You are given the roots root1 and root2 of two binary trees. Imagine laying one over the other, root on root. Merge them into one tree: where both trees have a node in the same position, the merged node's value is the sum of the two; where only one tree has a node, that node (with its whole subtree) is used as it is.

Return the root of the merged tree. Merging starts at the roots.

Example 1

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]
Explanation: Overlapping positions add up (1+2, 3+1, 2+3); 5 exists only in the first tree, 4 and 7 only in the second.

Example 2

Input: root1 = [1], root2 = [1,2]
Output: [2,2]

Example 3

Input: root1 = [], root2 = [4,null,-6]
Output: [4,null,-6]
Explanation: With one tree empty, the merge is just the other tree.

Constraints

  • The number of nodes in both trees is in the range [0, 2000]
  • -10^4 <= Node.val <= 10^4

Hints for Merge Two Binary Trees

  1. Hint 1

    Merge position by position, starting at the two roots.

  2. Hint 2

    If one of the two nodes is missing, the answer for this position is simply the other node — its whole subtree comes along unchanged.

  3. Hint 3

    Otherwise add the values and merge the left children with each other and the right children with each other.

How to solve Merge Two Binary Trees

Walk both trees together. Where both have a node, add the second's value into the first and recurse on the child pairs; where one side is missing, reuse the other side's subtree as it stands.

Approach

  1. If root1 is null return root2; if root2 is null return root1.
  2. Set root1.val += root2.val.
  3. Set root1.left = merge(root1.left, root2.left) and root1.right = merge(root1.right, root2.right).
  4. Return root1.

Why it works

Every position that exists in either tree is reached: positions present in both are handled by the summing case, and a position present in only one tree lies in a subtree that is attached whole by a base case — its nodes need no change, because there is nothing to add to them.

Complexity

  • Time — O(min(n, m)) — the walk only continues where both trees have nodes
  • Space — O(h) recursion depth

Pitfalls

  • Do not stop at the first missing node on one side; the other side's subtree must be kept.
  • Merging into root1 in place modifies the input — build new nodes if the inputs must stay intact.

Reference solution

Python

from typing import Optional

def mergeTrees(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 = mergeTrees(root1.left, root2.left)
    root1.right = mergeTrees(root1.right, root2.right)
    return root1

Java

public static TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if (root1 == null) return root2;
    if (root2 == null) return root1;
    root1.val += root2.val;
    root1.left = mergeTrees(root1.left, root2.left);
    root1.right = mergeTrees(root1.right, root2.right);
    return root1;
}

C++

TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    if (!root1) return root2;
    if (!root2) return root1;
    root1->val += root2->val;
    root1->left = mergeTrees(root1->left, root2->left);
    root1->right = mergeTrees(root1->right, root2->right);
    return root1;
}

JavaScript

var mergeTrees = function(root1, root2) {
    if (root1 === null) return root2;
    if (root2 === null) return root1;
    root1.val += root2.val;
    root1.left = mergeTrees(root1.left, root2.left);
    root1.right = mergeTrees(root1.right, root2.right);
    return root1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)