The problem. You are given two binary trees a and b. Imagine laying one on top of the other. Where both trees have a node, the merged node's value is the sum of the two. Where only one tree has a node, that node (with everything under it) is used as it is. Return the merged tree.
![Merging a = [1, 3, 2, 5] with b = [2, 1, 3, null, 4, null, 7]. Overlapping positions add up: 1+2 = 3, 3+1 = 4, 2+3 = 5. Positions only in a (5) or only in b (4 and 7) are copied over. The result is [3, 4, 5, 5, 4, null, 7].](/drawings/dee0ae98-0655-4830-be7b-3f703c1964a7.svg)
Input: a = [1, 3, 2, 5], b = [2, 1, 3, null, 4, null, 7]
Output: [3, 4, 5, 5, 4, null, 7]
Input: a = [1], b = [1, 2] Output: [2, 2]The two trees must be walked in step: the same position in both at once — root with root, left child with left child. It's the Same Tree walk, combining instead of comparing.
Free account
Sign up to read the rest of this lesson: 6 more sections, 2 drawings, a dry-run simulator and code in JavaScript, Python, Java and C++.
Still to come