Merge Two Binary Trees
Problem
Given two binary trees root1 and root2, merge them: where both trees overlap, sum the node values; where only one tree has a node, use that subtree as-is.
root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7][3,4,5,5,4,null,7]def merge_trees(t1, t2):
if not t1:
return t2
if not t2:
return t1
t1.val += t2.val
t1.left = merge_trees(t1.left, t2.left)
t1.right = merge_trees(t1.right, t2.right)
return t1function mergeTrees(t1, t2) {
if (!t1) return t2;
if (!t2) return t1;
t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null) return t2;
if (t2 == null) return t1;
t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
}TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (!t1) return t2;
if (!t2) return t1;
t1->val += t2->val;
t1->left = mergeTrees(t1->left, t2->left);
t1->right = mergeTrees(t1->right, t2->right);
return t1;
}Explanation
Merging two trees is naturally recursive: at each matching position we either combine two nodes or, if only one tree has a node there, we just take whatever exists. We walk both trees together with one DFS.
The two early checks do the heavy lifting. If t1 is missing, the merged result at this spot is simply t2 (and vice versa). This means an entire missing subtree is adopted as-is with no extra work.
When both nodes exist, we add their values with t1.val += t2.val, then recurse into the matching left children and the matching right children, reusing t1 as the merged tree.
Because we stop descending as soon as one side runs out, the work is proportional to the smaller overlapping region of the two trees.
Example: root1 = [1,3,2,5] and root2 = [2,1,3,null,4,null,7]. The roots sum to 1 + 2 = 3; where only one tree has a child (like the 7), that subtree is kept directly, producing [3,4,5,5,4,null,7].