How to Answer: Can you merge binary trees?
Advice and answer examples written specifically for a JavaScript Intermediate Level Tree job interview.
2. Can you merge binary trees?
This interview question concentrates on using JavaScript functions.
You are given root nodes root1 and root2 of two binary trees. Your task to merge them to form a new binary tree. The merge rules are as follows:
1. if both the trees have nodes at a specific position, the merged tree will have a node with a value equal to the sum of those two nodes at that position.
root1- 1 root2- 4
/ \ / \
2 3 5 6
merged- 5
/ \
7 9
At position “rootâ€- both trees have nodes. So node in the merged tree has value 1 + 4 = 5
At position “left of the rootâ€- both trees have nodes. So node in the merged tree has value 2 + 5 = 7
At position “right of the rootâ€- both trees have nodes. So node in the merged tree has value 3 + 6 = 9
2. if one tree has null and the other tree has a node at a specific position. the merged tree will have a node with a value equal to the value of the node of the other tree.
root1- 1 root2- 4
/ \
2 6
merged- 5
/ \
2 6
At position “left of the rootâ€- root1 has a node with value 2 but root2 doesn’t have a node. The merged tree has 2 at that position.
At position “right of the rootâ€- root2 has a node with value 6 but root1 doesn’t have a node. The merged tree has 6 at that position.
3. If both the trees have null at a specific position, then the merged tree too will have null at that position.
NOTE- You need to create a new tree. You can not modify the original trees.
/*Example*/
root1- 1 root2- 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
merged- 3
/ \
4 5
/ \ \
5 4 7
Solution:
We will use a recursive approach for this:
1. if both the nodes are null, we return null;
2. if one of them is null, we create newRoot with the value of the non-null node. Then we merge the left and right subtrees recursively;
3. if none of them is null, we create newRoot with a value equal to the sum of both nodes and then merge the left and right subtrees recursively.
class Node {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {Node} root1
* @param {Node} root2
* @return {Node}
*/
function mergeTrees(root1, root2) {
if (root1 === null && root2 === null) {
return null
}
let newRoot
if (root1 === null) {
newRoot = new Node(root2.val)
newRoot.left = mergeTrees(null, root2.left)
newRoot.right = mergeTrees(null, root2.right)
} else if (root2 === null) {
newRoot = new Node(root1.val)
newRoot.left = mergeTrees(root1.left, null)
newRoot.right = mergeTrees(root1.right, null)
} else {
newRoot = new Node(root1.val + root2.val)
newRoot.left = mergeTrees(root1.left, root2.left)
newRoot.right = mergeTrees(root1.right, root2.right)
}
return newRoot
}Time complexity- O(max(number of nodes in both trees))
Space complexity- O(max(height of both trees))
The code can be improved by using optional chaining and short-circuiting using OR operator.
class Node {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {Node} root1
* @param {Node} root2
* @return {Node}
*/
function mergeTrees(root1, root2) {
if (!root1 && !root2) {
return null
}
const val1 = root1?.val || 0
const val2 = root2?.val || 0
const newRoot = new Node(val1 + val2)
newRoot.left = mergeTrees(root1?.left, root2?.left)
newRoot.right = mergeTrees(root1?.right, root2?.right)
return newRoot
}Written by S. Kumar on May 22nd, 2021