Merge Two Binary Trees
Easy · Trees · Tree · Depth-First Search · Binary Tree
Problem
You are given two binary trees, root1 and root2. Picture laying one on top of the other.
Merge them position by position into one tree: where both trees have a node, the merged node's value is the sum of the two values; where only one tree has a node, that node (and everything below it) is used as it is.
The merge starts at the two roots. Return the root of the merged tree.
Examples
Input: root1 = [2,1,4], root2 = [3,null,5,null,6] Output: [5,1,9,null,null,null,6]
The roots add up to 5 and the right children to 9. The 1 and the 6 have no partner, so they are copied as they are.
Input: root1 = [], root2 = [8,3] Output: [8,3]
With one tree empty, the merge is the other tree.
Constraints
- The number of nodes in each tree is in the range [0, 2000]
- -10^4 <= Node.val <= 10^4
Approaches
- Sum values by path, then rebuild — time O(n · h), space O(n · h)
Follow-up
What if the trees can be thousands of levels deep, so recursion would overflow the stack? Walk them with an explicit stack of node pairs: pop a pair, add the values, and push the child pairs where both sides exist, attaching the lone child directly where only one does.
Related problems
Start free on Cariara · Coding problems · System design studio
