Difficulty: Easy, Asked-in: Amazon, Adobe, Hike
Key takeaway: An excellent problem to learn problem-solving using iterative and recursive pre-order traversals.
Given two binary trees with root nodes root1 and root2, write a program to merge them into a single binary tree.
Important note: before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!
Examples
Input:
Tree 1 Tree 2
6 3
/ \ / \
4 4 6 1
/ / \ \
5 3 2 7
Output: Merged tree
9
/ \
10 5
/ \ \
8 2 7
Solution Idea
The idea is to visit each node of the input binary trees using preorder traversal and check their existence in both the trees. If current nodes in both trees are not null then we add their values and update the current node value in the first tree. At the end of the traversal, the first tree will be the output i.e. merged binary tree.
Solution Steps
Solution Pseudocode
TreeNode mergeTrees(TreeNode root1, TreeNode root2)
{
if (root1 == null)
return root2
if (root2 == null)
return root1
root1->data = root1->data + root2->data
root1->left = mergeTrees(root1->left, root2->left)
root1->right = mergeTrees(root1->right, root2->right)
return root1
}
Time and space complexity analysis
Suppose the number of nodes is m and n in both trees. So in the worst case, we recursively visit min(m, n) nodes and perform O(1) operations with each node. Time complexity = O(min(m, n))
In the worst case, the depth of the recursion tree can go up to min(m, n) in the case of a skewed tree. Space complexity = O(min(m, n))
Solution Idea
Now we can try to solve the problem by traversing both trees iteratively in a preorder fashion. The question here is to merge both trees so we track nodes of both trees simultaneously using stack. For this, each entry in the stack stores data in the form of a pair of nodes: {nodetree1, nodetree2}. Here, nodetree1 and nodetree2 are the nodes of the first tree and the second tree respectively.
Solution Steps
Now we run a loop till the stack is not empty. At each step of iteration:
Solution Pseudocode
TreeNode mergeTrees(TreeNode root1, TreeNode root2)
{
if (root1 == null)
return root2
Stack <TreeNode[]> stack
TreeNode[] temp = {root1, root2}
stack.push(temp)
while (!stack.isEmpty())
{
temp = stack->pop()
if (temp[0] == null || temp[1] == null)
continue
temp[0]->val = temp[0]->val + temp[1]->val
if (temp[0]->left == null)
temp[0]->left = temp[1]->left
else
{
TreeNode[] curr = {temp[0]->left, temp[1]->left})
stack.push(curr)
}
if (temp[0]->right == null)
temp[0]->right = temp[1]->right
else
{
curr = {temp[0]->right, temp[1]->right}
stack.push(curr)
}
}
return root1
}
Time and space complexity analysis
Suppose the number of nodes is m and n in both trees. So in the worst case, we visit min(m, n) nodes and perform O(1) operations with each node. Time complexity = O(min(m, n))
In the worst case, the size of the stack space is min(m, n) (case of a skewed tree). Space complexity = O(min(m, n))
Solution Idea
One idea is clear: to merge both trees, we need to access each node of both trees in the same order and sum their corresponding node's values. So we can also think to solve this problem using BFS or level order traversal where we merge both trees in level by level fashion.
The implementation idea is quite similar to the above approach but we use the queue data structure to track the order of nodes and merge their values.
Solution Pseudocode
TreeNode mergeTrees(TreeNode root1, TreeNode root2)
{
if (root1 == null)
return root2
Queue <TreeNode[]> queue
TreeNode[] temp = {root1, root2}
queue.enqueue(temp)
while (!stack.isEmpty())
{
temp = queue.dequeue()
if (temp[0] == null || temp[1] == null)
continue
temp[0]->val = temp[0]->val + temp[1]->val
if (temp[0]->left == null)
temp[0]->left = temp[1]->left
else
{
TreeNode[] curr = {temp[0]->left, temp[1]->left})
queue.enqueue(curr)
}
if (temp[0]->right == null)
temp[0]->right = temp[1]->right
else
{
curr = {temp[0]->right, temp[1]->right}
queue.enqueue(curr)
}
}
return root1
}
Time and space complexity analysis
Suppose the number of nodes is m and n in both trees. So in the worst case, we visit min(m, n) nodes and perform O(1) operations with each node. Time complexity = O(min(m, n))
Important note: we recommend transforming the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verifying all the test cases. Enjoy programming!
Please write in the message below if you find anything incorrect, or you want to share more insight, or you know some different approaches to solve this problem. Enjoy learning, Enjoy algorithms!
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.