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!
Given an array X[] of n integers, return true if and only if it is a valid mountain array. The array X[] is a mountain array if and only if n >= 3 and there exists some i with 0 < i < n - 1 such that: X[0] < X[1] <...X[i-1] < X[i] and X[i] > X[i+1] > ...> X[n - 1]. In other words, we call the array mountain array when the array is strictly increasing and then strictly decreasing.
You are given an array of 1s and 0s and you are given an integer k which signifies the number of flips allowed. Write a program to find the position of zeros which when flipped will produce maximum continuous series of 1s.This is one of the good problems to understand the idea of the sliding window technique. Using this approach, We can solve several interview problems efficiently in O(n) and O(1) space.
A Segment Tree is a data structure used to answer multiple range queries on an array efficiently. Also, it allows us to modify the array by replacing an element or an entire range of elements in logarithmic time. This blog will focus on the build and query operations on segment trees.
Given an array X[] of distinct elements, write a program to find all the unique triplets in the array whose sum is equal to zero. For example, suppose such triplets in the array are X[i], X[j] and X[k] then X[i] + X[j] + X[k] = 0. Note : solution set must not contain duplicate triplets.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.