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.
- Difficulty: Easy
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Microsoft, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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
Hint 1
Merge position by position, starting at the two roots.
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.
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
- If
root1is null returnroot2; ifroot2is null returnroot1. - Set
root1.val += root2.val. - Set
root1.left = merge(root1.left, root2.left)androot1.right = merge(root1.right, root2.right). - 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
root1in 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 root1Java
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)