Watch 10 video solutions for Merge Two Binary Trees, a easy level problem involving Tree, Depth-First Search, Breadth-First Search. This walkthrough by NeetCode has 69,156 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT 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.
Example 1:
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] Output: [3,4,5,5,4,null,7]
Example 2:
Input: root1 = [1], root2 = [1,2] Output: [2,2]
Constraints:
[0, 2000].-104 <= Node.val <= 104Problem Overview: You receive two binary trees. If two nodes overlap, their values are summed. If only one node exists at a position, that node becomes part of the merged tree. The goal is to return the root of the merged tree.
Approach 1: Recursive Depth-First Search (O(n) time, O(h) space)
This approach uses recursion to traverse both trees simultaneously. For each pair of nodes, add their values and recursively merge their left and right children. If one node is null, return the other node directly. The recursion naturally follows the structure of the trees, making the implementation concise and easy to reason about. Time complexity is O(n) where n is the total number of nodes across both trees, because each node is processed once. Space complexity is O(h) from the recursion stack, where h is the height of the tree.
This approach directly leverages Depth-First Search traversal on a Binary Tree. It modifies or builds nodes as the recursion unwinds.
Approach 2: Iterative Traversal with Queue or Stack (O(n) time, O(n) space)
An iterative strategy avoids recursion by explicitly managing traversal with a queue (BFS) or stack (DFS). Start with the pair of root nodes. While the data structure is not empty, pop a node pair and merge their values. For children, if both nodes exist, push the pair for later processing. If a child exists in only one tree, attach it directly to the merged tree. This simulates the recursive traversal but uses an explicit structure to track work.
The algorithm still processes each node once, giving O(n) time complexity. Space complexity becomes O(n) in the worst case due to the queue or stack holding node pairs. Using a queue corresponds to Breadth-First Search, which processes the tree level by level.
Recommended for interviews: The recursive DFS solution is the expected answer. It clearly shows understanding of binary tree traversal and keeps the code minimal. Interviewers often look for the base-case handling (null nodes) and correct recursive merging of children. The iterative version demonstrates deeper control over traversal mechanics and is useful when recursion depth might be a concern.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search | O(n) | O(h) | Best general solution. Clean code and natural fit for binary tree recursion. |
| Iterative Traversal (Queue/Stack) | O(n) | O(n) | Useful when avoiding recursion or when recursion depth may cause stack overflow. |