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!
Input:
Tree 1 Tree 2
6 3
/ \ / \
4 4 6 1
/ / \ \
5 3 2 7
Output: Merged tree
9
/ \
10 5
/ \ \
8 2 7
To merge two binary trees, we want to visit each node of the input trees and combine them in some way. One way to do this is to use a preorder traversal, which means that we visit the root of the tree, then the left child, and then the right child.
As we visit each node, we check if it exists in both trees. If the nodes exist in both trees, we add their values and update the current node value in the first tree. If one of the tree node is null, we update the current node value in the first tree with the value of other node.
By following this process for each node in the input trees, we can combine the trees into a single tree, where resulting tree will be the first tree.
Base case: If either of the input trees is null, we return the root of the other tree. Otherwise, we sum the values of the roots of the two trees and update the root of the first tree with this sum.
if (root1 == NULL)
return root2
if (root2 == NULL)
return root1
root1->data = root1->data + root2->data
TreeNode* mergeBinaryTrees(TreeNode* root1, TreeNode* root2)
{
if (root1 == NULL)
return root2;
if (root2 == NULL)
return root1;
root1->data = root1->data + root2->data;
root1->left = mergeBinaryTrees(root1->left, root2->left);
root1->right = mergeBinaryTrees(root1->right, root2->right);
return root1;
}
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))
The idea behind the solution is to iteratively traverse both trees in a preorder fashion, combining their nodes as we go. To do this, we will track nodes from both trees simultaneously using a stack, where each entry in the stack consists of a pair of nodes: {node from tree 1, node from tree 2}.
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2)
{
if (root1 == NULL)
return root2;
stack<pair<TreeNode*, TreeNode*>> stack;
stack.push({root1, root2});
while (stack.empty() == false)
{
auto temp = stack.top();
stack.pop();
if (temp.first == NULL || temp.second == NULL)
continue;
temp.first->val = temp.first->val + temp.second->val;
if (temp.first->left == NULL)
temp.first->left = temp.second->left;
else
stack.push({temp.first->left, temp.second->left});
if (temp.first->right == NULL)
temp.first->right = temp.second->right;
else
stack.push({temp.first->right, temp.second->right});
}
return root1;
}
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))
The idea behind this solution is to merge both trees by accessing and summing the values of each corresponding node in the same order. One way to do this is using a breadth-first search (BFS) or level order traversal, where we merge the trees level by level.
To implement this solution, we can use a queue data structure to track the order of nodes and merge their values. This approach is similar to the previous solution, but instead of using a stack, we use a queue to track the nodes in a level-by-level fashion.
We start by checking if root1 is NULL. If it is, we return root2. Otherwise, we create a queue and insert a pair consisting of root1 and root2 into the queue.
Next, we run a loop that continues as long as the queue is not empty.
Finally, at the end of the loop, we return root1 as the output.
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2)
{
if (root1 == NULL)
return root2;
queue<pair<TreeNode*, TreeNode*>> queue;
queue.emplace(root1, root2);
while (queue.empty() == false)
{
auto temp = queue.front();
queue.pop();
if (temp.first == NULL || temp.second == NULL)
continue;
temp.first->val = temp.first->val + temp.second->val;
if (temp.first->left == NULL)
temp.first->left = temp.second->left;
else
queue.emplace(temp.first->left, temp.second->left);
if (temp.first->right == NULL)
temp.first->right = temp.second->right;
else
queue.emplace(temp.first->right, temp.second->right);
}
return root1;
}
def mergeTrees(root1, root2):
if not root1:
return root2
queue = collections.deque()
queue.append((root1, root2))
while queue:
n1, n2 = queue.popleft()
if not n1 or not n2:
continue
n1.val = n1.val + n2.val
if not n1.left:
n1.left = n2.left
else:
queue.append((n1.left, n2.left))
if not n1.right:
n1.right = n2.right
else:
queue.append((n1.right, n2.right))
return root1
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))
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 well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.