Merge Two Binary Trees
The key idea
Walk both trees in lockstep with one recursion. At each position, if either node is missing return the other; otherwise build a new node holding the sum and recurse into the matched left pair and the matched right pair.
Problem
You are given two binary trees root1 and root2.
Imagine that when you put one of them to cover the other, some nodes of the two trees overlap while the others do not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum the node values up as the new value of the merged node. Otherwise, the non-null node will be used as the node of the new tree.
Return the merged tree.
Note: The merging process must start from the root nodes of both trees.
Constraints
- The number of nodes in both trees is in the range
[0, 2000]. -10^4 <= Node.val <= 10^4
Examples
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]
Input: root1 = [1], root2 = [1,2]
Output: [2,2]
Complexity
Time: O(n) Space: O(h)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY