Merge Two Binary Trees - Solution & Explanation
Problem Statement
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:
- The number of nodes in both trees is in the range
[0, 2000]. -104 <= Node.val <= 104
Approach Overview
Problem 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 1: Recursive Approach
This approach utilizes recursion to traverse both trees simultaneously. If both node values are non-null, we sum them up as the new value and recursively merge their left and right children. If one node is null, we return the non-null node.
This C solution uses a recursive function mergeTrees. We check if either of the current nodes is null and return the other node. If neither is null, we sum their values, then recursively merge their left and right children.
Complexity
Time Complexity: O(n); Space Complexity: O(h), where n is the total number of nodes and h is the height of the tree.
Approach 2: Iterative Approach
This approach uses an iterative method with a stack to simulate the recursive calls for merging the two binary trees. We traverse the trees using a stack and merge nodes at each level iteratively.
This C solution uses a stack to perform an iterative merge of the binary trees. We manage pairs of nodes to process, summing their values and pushing their children onto the stack for subsequent processing.
Complexity
Time Complexity: O(n); Space Complexity: O(h), where n is the total number of nodes and h is the maximum height of the two trees.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n); Space Complexity: O(h), where n is the total number of nodes and h is the height of the tree. |
| Iterative Approach | Time Complexity: O(n); Space Complexity: O(h), where n is the total number of nodes and h is the maximum height of the two trees. |
| Default Approach | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Merge Two Binary Trees - Leetcode 617 • NeetCode • 70,833 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Merge Two Binary Trees easy or hard?
Merge Two Binary Trees Python/Java solution
How to solve Merge Two Binary Trees in O(n)?
What is the best approach for Merge Two Binary Trees?
Is Merge Two Binary Trees asked at Google/Amazon/Meta?
What data structure is used in Merge Two Binary Trees?
What is the time complexity of Merge Two Binary Trees?
Ready to solve this problem?
Practice Merge Two Binary Trees with our built-in code editor and test cases.
Practice on FleetCode