Overlay Two Trees
EasyTrees
Problem
Two binary trees a and b are laid on top of each other, root on root. Where both trees have a node at the same position, the result has one node whose value is the sum of the two. Where only one tree has a node, the result takes that node (with everything below it) unchanged.
Return the root of the combined tree.
Example 1
- Input:
- a = [1, 3, 2, 5], b = [2, 1, 3, null, 4, null, 7]
- Output:
- [3, 4, 5, 5, 4, null, 7]
Roots 1 + 2 = 3, left 3 + 1 = 4, right 2 + 3 = 5; the 5 exists only in a, the 4 and 7 only in b.
Example 2
- Input:
- a = [1], b = [1, 2]
- Output:
- [2, 2]
Constraints
- 0 ≤ nodes in each tree ≤ 2000
- -10^4 ≤ node.val ≤ 10^4
Hint
Show the first hint
Solve it for the two roots first. What are the cases?
Walkthrough
How to approach it
01Clarify before coding
- Can I reuse nodes from the inputs? Yes; where only one tree has a subtree, return it as is.
- Can either tree be empty? Yes, both can.
- Does a zero sum remove a node? No, the node stays with value 0.
02Brute force
Convert both trees to complete position-indexed arrays, add them slot by slot and rebuild.
Cost: Position indexing doubles per level, so a deep, thin tree needs O(2^h) slots: exponential memory.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.