Difficulty: Easy, Asked-in: Amazon, Adobe, Hike.
Key takeaway: An excellent problem to learn problem-solving using pre-order and level order.
Given two binary trees with root nodes root1 and root2, write a program to merge them into a single binary tree. Imagine that when we put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
Input:
Tree 1 Tree 2
6 3
/ \ / \
4 4 6 1
/ / \ \
5 3 2 7
Output: Merged tree
9
/ \
10 5
/ \ \
8 2 7To merge two binary trees, we need to process the nodes at matching positions in both trees. So we traverse each position in both trees simultaneously using preorder. At each position:
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.
mergeBinaryTrees(root1, root2)
if root1 is null
return root2
if root2 is null
return root1
// Both nodes exist, so combine their values
root1.data = root1.data + root2.data
// Recursively merge the left and right subtrees
root1.left = mergeBinaryTrees(root1.left, root2.left)
root1.right = mergeBinaryTrees(root1.right, root2.right)
return root1Suppose 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). Space complexity = O(min(m, n)).
The idea behind the solution is to iteratively traverse both trees in preorder, 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}. Here each pair represents nodes at the same position in the two trees.
mergeTrees(root1, root2)
if root1 is null
return root2
stack = empty stack
push (root1, root2) onto stack
while stack is not empty
(node1, node2) = top of stack
pop stack
if node1 is null or node2 is null
continue
node1.val = node1.val + node2.val
if node1.left is null
node1.left = node2.left
else
push (node1.left, node2.left) onto stack
if node1.right is null
node1.right = node2.right
else
push (node1.right, node2.right) onto stack
return root1Suppose 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 is to merge both trees by accessing and adding the values of each corresponding node. One way to do this is using breadth-first search traversal, where we merge the trees level by level. To implement this, we can use a queue 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 nodes.
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.
Now 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.
mergeTrees(root1, root2)
if root1 is null
return root2
queue = empty queue
enqueue (root1, root2)
while queue is not empty
(node1, node2) = front of queue
dequeue queue
if node1 is null or node2 is null
continue
node1.val = node1.val + node2.val
if node1.left is null
node1.left = node2.left
else
enqueue (node1.left, node2.left)
if node1.right is null
node1.right = node2.right
else
enqueue (node1.right, node2.right)
return root1Suppose 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!