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.
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))
Enjoy learning, Enjoy Algorithms
Subscribe to get well-designed content on data structures and algorithms, machine learning, system design, oops, and mathematics. enjoy learning!
Write a program to Implement a queue using the stack. The implemented queue should support standard operations like enqueue, dequeue, and front. This is an excellent problem to learn problem-solving and visualize the use case of stack and queue operations.
EnjoyAlgorithms
In recursive DFS traversals of a binary tree, we have three basic elements to traverse— root, left subtree, and right subtree. The traversal order depends on the order in which we process the root node. Here recursive code is simple and easy to visualize — only one function parameter and 3–4 lines of code. So critical question would be — How can we convert it into iterative code using stack? To simulate the recursive traversal into an iterative traversal, we need to understand the flow of recursive calls.
EnjoyAlgorithms