Similar Problems
Similar Problems not available
Merge Two Binary Trees  Leetcode Solution
LeetCode: Merge Two Binary Trees Leetcode Solution
Difficulty: Easy
Topics: binarytree tree depthfirstsearch breadthfirstsearch
Problem:
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:
Input:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
Output: Merged tree:
3
/ \
4 5
/ \ \
5 4 7
Solution:
This problem can be solved using recursion. We will create a new tree which will have the sum of the nodes of the two trees.

Create a new tree whose root will have the sum of the roots of the two trees.

Recursively for the left subtree of the root of the new tree, call mergeTrees function by passing the left child of root1 and the left child of root2.

Recursively for the right subtree of the root of the new tree, call mergeTrees function by passing the right child of root1 and the right child of root2.

Return the new tree.
Here is the Python code snippet:
class Solution:
def mergeTrees(self, root1: TreeNode, root2: TreeNode) > TreeNode:
if root1 is None:
return root2
if root2 is None:
return root1
root1.val += root2.val
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1
Time Complexity: O(n), where n is the number of nodes in the bigger tree.
Space Complexity: O(h), where h is the height of the tree. In the worst case, if the trees are skewed, the height can be n, thus space complexity becomes O(n).
Merge Two Binary Trees Solution Code
1