14 JavaScript Intermediate Level Tree Interview Questions & Answers
Below is a list of our JavaScript Intermediate Level Tree interview questions. Click on any interview question to view our answer advice and answer examples. You may view 5 answer examples before our paywall loads. Afterwards, you'll be asked to upgrade to view the rest of our answers.
1. Is the binary tree symmetric?
This interview question concentrates on using JavaScript recursive and iterative functions.
You are given a binary tree. You have to check if the tree is symmetric about its center.
A tree is symmetric when the left subtree and the right subtree of the root node are mirror images of each other as shown in the example below.
/*Example*/
10
/ |\
15 | 15
/ \ | / \
1 2 | 2 1
The above tree is symmetric about its centre. So we will return true.
10
/ |\
1 | 1
/ \ | \
2 | 2
The above tree is not symmetric about its centre. So we will return false.Solution:
Approach I (Recursive):
For two nodes to be a mirror of each other, either they both should be non-null or both null. If only one of them is null, they are definitely not a mirror of each other.
If the nodes are non-null,
1. their value must be equal,
2. the left subtree of the first node must be the mirror of the right subtree of the second node,
3. the right subtree of the first node must be the mirror of the left subtree of the second node.
class Node {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {Node} root
* @return {boolean}
*/
function isTreeSymmetric(root) {
if (!root) return true
return isMirror(root.left, root.right)
}
function isMirror(node1, node2) {
if (!node1 && !node2) return true
if (!node1 || !node2) return false
return(
node1.val === node2.val &&
isMirror(node1.left, node2.right) &&
isMirror(node1.right, node2.left)
)
}Time complexity- O(number of nodes)
Space complexity- O(height of tree)
Approach II (Iterative):
The approach is almost the same as the recursive approach. We just use stack instead of recursion to keep track of nodes that we want to compare to check if they are the mirror of each other or not.
We maintain a stack array. First, we push two nodes left and right of the root node. Then in every iteration, we pop two nodes from the stack. Then we check the null-ness of both nodes. If they both are null, we continue two check other nodes in the stack.
If only one of them is null, we straightaway return false.
Then we compare their value. If values are equal, we push their children nodes in a specific order as with the recursive approach.
class Node {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {Node} root
* @return {boolean}
*/
function isTreeSymmetric(root) {
if (!root) return true
const stack = []
stack.push(root.left)
stack.push(root.right)
while(stack.length !== 0) {
const node1 = stack.pop()
const node2 = stack.pop()
if (!node1 && !node2) continue
if (!node1 || !node2) return false
if (node1.val != node2.val) return false
stack.push(node1.left)
stack.push(node2.right)
stack.push(node1.right)
stack.push(node2.left)
}
return true
}Time complexity- O(number of nodes)
Space complexity- O(height of tree)
Written by S. Kumar on May 22nd, 2021
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
3. How do you increase the skewed tree?
This interview question concentrates on using JavaScript binary search tree.
You are given the root node of a binary search tree. Your task is to rearrange the tree such that:
1. the root is the node with the smallest value, and
2. every node has no left child, only right child, and
3. every parent node is smaller than its right child.
/*Example*/
Given tree-
5
/ \
3 8
/ / \
2 6 9
/ \
1 7
Expected
1
2
3
4
5
6
7
8
9
Solution:
We know that in a BST (binary search tree), the inorder traversal returns nodes in increasing order. We will create a list of all the nodes in the tree in increasing order using inorder traversal.
After that, we will iterate over the list. and will set the left of each node to null and set the right of the current node to the next node.
class Node {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {Node} root
* @return {Node}
*/
function toRightSkewedBst(root) {
const inOrderTraversal = []
inOrder(root, inOrderTraversal)
// remove left child, if any
inOrderTraversal[0].left = null
for (let i = 1; i < inOrderTraversal.length; i++) {
inOrderTraversal[i - 1].right = inOrderTraversal[i]
// remove left child, if any
inOrderTraversal[i].left = null
}
return inOrderTraversal[0]
}
function inOrder(root, inOrderTraversal) {
if (!root) return
inOrder(root.left, inOrderTraversal)
inOrderTraversal.push(root)
inOrder(root.right, inOrderTraversal)
}n = number of nodes in both trees
Time complexity- O(n)
Space complexity- O(n)
Written by S. Kumar on May 22nd, 2021
4. Invert the binary tree.
This interview question concentrates on using JavaScript binary tree inversion through iteration and recursion.
Given the root of a binary tree, invert the tree, and return its root.
For a tree to be inverted the left child of every node has to be swapped with the right child.
/*Example*/
4
/ \
2 7
/ \ / \
1 3 6 9
Inverting the above tree.
4
/ \
7 2
/ \ / \
9 6 3 1
Solution:
Let’s replicate the inverting process for the given sample tree:
Traverse through the tree and for every node, we swap its left subtree with the right subtree.
4
/ \
2 7
We are currently at node 4. We swap the left subtree (2) with the right subtree(7)
4
/ \
7 2
/ \ / \
6 9 1 3
We now invert the subtrees rooted at nodes 2 and 7.
Repeat the same process for nodes 7 and 2. Note that we do not need to repeat this process for leaf nodes as they don’t have any left and right children.
4
/ \
7 2
/ \ / \
9 6 3 1
Approach I (Recursive):
We can solve the problem recursively. For each node, we first recursively invert the left and right subtrees. Then we swap the left and right subtree with each other.
class Node {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {Node} root
* @param {number} low
* @param {high} low
* @return {number}
*/
function invertTree(root) {
if (root === null) return root;
const leftNode = invertTheTree(root.left);
const rightNode = invertTheTree(root.right);
root.right = leftNode;
root.left = rightNode;
return root;
}Time complexity- O(n) where n is the number of nodes
Space complexity- O(h) where h is the height of the tree
Approach II (Iterative):
This approach is similar to a recursive one. We first swap the left and right children of the root. Now instead of recursively calling the invert function, we push both these nodes to a stack. This stack contains nodes whose children haven’t been swapped.
In each iteration, we pop one node from the stack. We swap its left and right children and add them to the stack if they exist. We repeat this process until all nodes are processed and their children are inverted.
class Node {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {Node} root
* @param {number} low
* @param {high} low
* @return {number}
*/
function invertTree(root) {
if (root === null) return root;
const stack = [];
stack.push(root);
while (stack.length !== 0) {
const node = stack.pop();
const leftNode = node.left;
node.left = node.right;
node.right = leftNode;
if (node.left !== null) {
stack.push(node.left);
}
if (node.right !== null) {
stack.push(node.right);
}
}
return root;
}Time complexity- O(n) where n is the number of nodes
Space complexity- O(n) where n is the number of nodes
Written by S. Kumar on May 22nd, 2021
5. Are the two binary trees the same or not?
This interview question concentrates on using JavaScript recursion and iteration.
Given the roots of two binary trees node1 and node2, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
/*Example 1*/
4
/ \
1 2
4
/ \
2 1
False, the left node of 4 is 1 in the first tree but is 2 in the next.
/*Example 2*/
5
/ \
7 8
/ \
4 2
5
/ \
7 8
/ \
4 2
True, All the values are the same and they are identical Approach I (Recursive):
For two trees to be identical. All the values must be the same and they should be structurally similar. That is if values exist at one tree they must also exist on the other and vice versa.
We will visit all the nodes of both the trees starting with the root nodes.
We compare the similarity of the root nodes. If they don’t have the same value we return false. Otherwise, we recursively check for the similarity of the right and left subtree.
Return true if all the conditions are met else return false.
class Node {
constructor(val, left, right) {
this.val = val || 0;
this.left = left || null;
this.right = right || null;
}
}
/* @param {TreeNode} node1
* @param {TreeNode} node2
* @return {boolean}
*/
function sameTree(node1, node2) {
if (!node1 && !node2) return true;
if (!node1 || !node2) return false;
const isLeftTreeSame = sameTree(node1.left, node2.left);
const isRightTreeSame = sameTree(node1.right, node2.right);
const isSame = node1.val === node2.val
&& isLeftTreeSame && isRightTreeSame;
return isSame;
}Time complexity- O(n) where n is the number of nodes in the tree
Space complexity- O(n)
Approach II (Iterative):
This approach is similar to a recursive one. We first check the similarity of the root nodes of both the trees. Now instead of recursively calling the similarity function, we push both these nodes to a stack. This stack contains nodes whose children haven’t been checked for similarity.
In each iteration, we pop two nodes from the stack. We first check for their similarity and then check for the similarity of their left and right children. If both the children are similar we add them to the stack if they exist. We repeat this process until all nodes are processed.
In the end, we return the true else we return false during iteration if any of the conditions aren’t met.
class Node {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {Node} root
* @param {number} low
* @param {high} low
* @return {number}
*/
function sameTree(node1, node2) {
if (!node1 && !node2) return true;
if (!node1 || !node2) return false;
let stack = [node1, node2];
while (stack.length) {
const subnode2 = stack.pop();
const subnode1 = stack.pop();
//If the values of the nodes aren't equal
if (subnode2.val !== subnode1.val) return false;
if (subnode1.left && subnode2.left) {
//If left subsubnode exists
stack.push(subnode1.left);
stack.push(subnode2.left);
} else if (subnode1.left || subnode2.left) {
//If one of the left subsubnode is null
return false;
}
if (subnode1.right && subnode2.right) {
//If right subsubnode exists
stack.push(subnode1.right);
stack.push(subnode2.right);
} else if (subnode1.right || subnode2.right) {
//If one of the right subsubnode is null
return false;
}
}
return true;
}Time complexity- O(n) where n is the number of nodes in the tree
Space complexity- O(n)
Written by S. Kumar on May 22nd, 2021
6. What is the maximum depth of the binary tree?
This interview question concentrates on using JavaScript functions using recursion and iteration.
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
/*Example*/
4
/ \
1 2
/ \
9 10
The depth of the tree is 3Solution:
4
If only a single node was given to us we would have returned its depth as 1
4
/ \
1 2
The max depth of the above tree is 2. 1 root + 1 depth of child
4
/ \
1 2
/
9
The max depth of the above tree is 3. 4 -> 2 -> 9
Depth from the left node(1) is 2
Depth from the right node(2) is 3
You can notice that the max depth is the maximum depth out of the left and the right nodes of the root and adding 1 to it (root depth=1)
Hence maxDepth = max(leftNodeDepth,rightNodeDepth) + 1
Approach I (Recursive):
We visit all the nodes of the tree starting with the root node. For each node, we recursively check the max depth of the left subtree and the right subtree if they exist.
In the end, we return one plus the max of the depth out of the left and right subtree.
class Node {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {Node} root
* @param {number} low
* @param {high} low
* @return {number}
*/
function maximumDepth(root) {
if (root == null) return 0;
const right = maximumDepth(root.right);
const left = maximumDepth(root.left);
return Math.max(left, right) + 1;
}Time complexity- O(n) where n is the number of the nodes in the tree
Space complexity- O(h) where h is the height of the tree
Approach II (Iterative):
This approach is similar to a recursive one. We first check if the root node exists. Now instead of recursively calling the max depth function, we push this node to a stack. This stack contains nodes whose children haven’t been checked for similarity.
Our stack should only be filled with nodes that are of the same level thus we maintain a variable s that stores the size of our stack. In each iteration, we pop s nodes from the stack and increment our max depth variable. Then we push the left and right children to the stack if they exist.
We repeat this process until all nodes are processed.
In the end, we return the max depth variable.
class Node {
constructor(val, left, right) {
this.val = val || 0;
this.left = left || null;
this.right = right || null;
}
}
/**
* @param {TreeNode} root
* @return {number}
*/
function maximumDepth(root) {
if (root === null) return 0;
let finalAns = 0;
const stack = [];
stack.push(root);
while (stack.length !== 0) {
finalAns++;
for (let i = 0, s = stack.length; i < s; i++) {
const node = stack.shift();
if (node.left !== null) {
stack.push(node.left);
}
if (node.right !== null) {
stack.push(node.right);
}
}
}
return finalAns;
}Time complexity- O(n) where n is the number of the nodes in the tree
Space complexity- O(n)
Written by S. Kumar on May 22nd, 2021
7. Using in-order traversal of the binary tree, return an array.
This interview question focuses on the developer's skills with JavaScript methods.
You are given a binary tree. Perform inorder traversal of the tree and return the result in the form of an array.
/*Example*/
Given tree:
1
/ \
2 3
/ / \
4 5 6
Expected output:- [4, 2, 1, 5, 3, 6]Solution:
Approach I (recursive):
We will make a helper function _inorderTraversal which also takes the result array. This function will, first, call on the left child recursively. Then it adds the value of the current node to the result array, and then recurse on the right child.
class TreeNode {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {TreeNode} root
* @return {number[]}
*/
function inorderTraversal(root) {
const result = []
_inorderTraversal(root, result)
return result
}
function _inorderTraversal(node, result) {
if (node === null) return
_inorderTraversal(node.left, result)
result.push(node.val)
_inorderTraversal(node.right, result)
}n = no of nodes in the tree
Time complexity- O(n)
Space complexity- O(n) // if the tree is a skewed tree
Approach II (iterative):
We will have two arrays: result and stack. The result array will be our final answer array. The stack array stores the nodes which need to be processed yet.
For a given node, we first go to the deepest leftmost child. For example:
1
/ \
2 3
/ / \
4 5 6
For node 1, the deepest leftmost child is 4
For node 3, deepest leftmost child is 5
Then, we pop a node from the stack and push its value to the result. Then we iterate over the right child of the popped node.
class TreeNode {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {TreeNode} root
* @return {number[]}
*/
function inorderTraversal(root) {
const result = []
const stack = []
let curr = root
while(curr !== null || stack.length !== 0) {
// find deepest leftmost child
// add push intermediate nodes
while(curr !== null) {
stack.push(curr)
curr = curr.left
}
// we have reached the leftmost child
curr = stack.pop()
result.push(curr.val)
// now iterate its right subtree
curr = curr.right
}
return result
}n = no of nodes in the tree
Time complexity- O(n)
Space complexity- O(n) // if the tree is a skewed tree
Written by S. Kumar on May 22nd, 2021
8. What is the lowest common ancestor in a binary search tree?
This question shows the developer's skills working with JavaScript loops.
You are given the root node of a binary search tree. You are also given nodes node1 and node2. Your task is to find and return the lowest common ancestor (LCA) of node1 and node2 in the given tree.
/*Example*/
Given tree:
6
/ \
2 8
/ \ / \
0 4 7 9
/ \
3 5
Given node1 = 0, node2 = 5
Expected output:- 2
Explanation: common ancestors of 0 and 5 are 2 and 6 out of which 2 is the lowest common ancestor.
LCA of 0 and 2 is 2
LCA of 2 and 3 is 2
LCA of 5 and 6 is 6
LCA of 3 and 5 is 4
LCA of 7 and 4 is 6Solution:
First, we need to make some observations. There are three cases for positions of the two nodes
CASE I:- when both are in the left subtree of some node
x1
/ \
node1 x
\
node2 Here LCA is node1
CASE II:- when both are in the right subtree of some node
x1
/ \
x node1
\
node2 Here LCA is node1
CASE III:- when both nodes are in different subtrees of a node
x1
/ \
node1 x
/
node2 Here LCA is x1
Since the given tree, it is easier to find in which case node1 and node2 lie with respect to a given node. We will traverse the BST starting from the root node of the tree recursively. During recursion, for a given node root,
1. if the values of both node1 and node2 less than the value of root, then node1 and node2 both lie on the left subtree of root;
2. if the values of both node1 and node2 greater than the value of root, then node1 and node2 both lie on the right subtree of root;
3. otherwise there is a split at the root node, thus the root node will be their LCA.
class TreeNode {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {TreeNode} root
* @param {TreeNode} node1
* @param {TreeNode} node2
* @return {TreeNode}
*/
function lowestCommonAncestor(root, node1, node2) {
const rootValue = root.val
const value1 = node1.val
const value2 = node2.val
if (value1 > rootValue && value2 > rootValue) {
// both are in right subtree
return lowestCommonAncestor(root.right, node1, node2)
} else if (value1 < rootValue && value2 < rootValue) {
// both are in left subtree
return lowestCommonAncestor(root.left, node1, node2)
} else {
return root
}
}n = no of nodes in the tree
Time complexity- O(n)
Space complexity- O(n) // if the tree is a skewed tree
Written by S. Kumar on May 22nd, 2021
9. Can you find the zigzag level order traversal of the node values?
This interview question concentrates on the developer's ability to work with or without JavaScript reversal.
You are given the root node of a binary tree. Your task is to return the zigzag level order traversal of its nodes' values. That zigzag level order traversal is first level from left to right (LTR), next from right to left (RTL) and so on.
/*Example*/
Given tree:
3
/ \
9 2
/ \
4 5
Expected output:- [[3], [2, 9], [4, 5]]
Explanation:
First level: [3] from left to right
Second level: [9, 2] => [2, 9] from right to left
Third level: [4, 5] from left to rightSolution:
Approach I (using reverse):
This is the easiest approach. We will find the level order of the tree and will reverse every other level order. previousLevel stores the nodes in level order of the previous level. Then we find the level order of the current level in currLevel. To find this, we will iterate over each node in previousLevel and push their left and right children to currLevel. After doing so, we will find the values of the current level in currLevelValues using Array.prototype.map method. If the current is supposed to be right to left (RTL), we reverse the values of currLevelValues using Array.prototype.reverse method. Then we store the values of the current level in the desired order to the result array. Then we proceed to the next level.
If the currLevel is empty, it means previousLevel was the last level in the binary tree. In this case, we break the loop.
class Node {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {Node} root
* @return {number[][]}
*/
function zigzagLevelOrder(root) {
if (!root) return []
const result = [[root.val]]
let previousLevel = [root]
let leftToRight = false
while(true) {
const currLevel = []
for (const node of previousLevel) {
if (node.left) currLevel.push(node.left)
if (node.right) currLevel.push(node.right)
}
if (currLevel.length == 0) break
const currLevelValues = currLevel.map(c => c.val)
if (!leftToRight) currLevelValues.reverse()
result.push(currLevelValues)
previousLevel = currLevel
leftToRight = !leftToRight
}
return result
}n = number of nodes in the tree
Time complexity- O(n)
Space complexity- O(n)
Approach II (without using reverse):
Reversing the array is less efficient. We can use stacks for the reverse effect. In this approach, we will have a stack (array in JavaScript) currentLevel which stores the nodes of the current level which we are traversing and pushing values. In each iteration, we retrieve the last node in currentLevel using Array.prototype.pop method. The variable leftToRight stores the direction of the next level. If it is true, it means the next level is supposed to be LTR direction and vice-versa. If the next level is supposed to be in LTR direction, we push the right child first then the left child, because while retrieving the node stack, the left child will come first which will be the correct order. And if the next level is supposed to be in the RTL direction, we push the left child first then the right child.
When the currentLevel is traversed, we
1. push its values to the result array,
2. reverse the direction of leftToRight
3. mark nextLevel to be currentLevel
4. and initialize new arrays for currLevelValues and nextLevel.
class Node {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {Node} root
* @return {number[][]}
*/
function zigzagLevelOrder(root) {
if (!root) return []
const result = []
let currLevelValues = []
let currentLevel = [root]
let nextLevel = []
let leftToRight = false
while (currentLevel.length > 0) {
const node = currentLevel.pop()
const left = node.left
const right = node.right
currLevelValues.push(node.val)
if (leftToRight) {
if (right) nextLevel.push(right)
if (left) nextLevel.push(left)
} else {
if (left) nextLevel.push(left)
if (right) nextLevel.push(right)
}
// finished current level
if (currentLevel.length === 0) {
result.push(currLevelValues)
leftToRight = !leftToRight
currLevelValues = []
currentLevel = nextLevel
nextLevel = []
}
}
return result
}n = number of nodes in the tree
Time complexity- O(n)
Space complexity- O(n)
Written by S. Kumar on May 22nd, 2021
10. How do you delete the key from the BST and return the modified tree root node?
This question shows the developer's ability to work with JavaScript recursion and iteration.
You are given the root node of a binary search tree (BST). Each node contains an integer value. You are also given an integer key. Your task is to delete the key from the given BST and return the root node of the modified tree.
/*Example*/
Given key = 3 and tree:
5
/ \
3 6
/ \ \
2 4 7
Expected output:
5
/ \
4 6
/ \
2 7
The following result is also accepted
5
/ \
2 6
\ \
4 7Solution:
Approach I (recursive):
In the recursive approach, we will compare the value of the current node with the key.
â— If the key is lesser, we will delete it in the left subtree;
â— if the key is greater, we will delete it in the right subtree.
If the key is equal to the value of the current node. We will delete this node. If this node does not have a left child, we will directly return its right child (this will make the desired node deleted). The same is true when it has only the left child, then we return the left child. If this node has both children, then we do a different procedure. First, we will find the node with minimum value in the right subtree (say it is minNode). Then we copy the value of the minNode to the node to be deleted. Then we delete minNode in the right subtree. In the following tree, (7) is the node with a minimum value in the right subtree of (5).
5 <--- (node to be deleted)
/ \
3 10
/ \
8 11
/ \
(minNode)-> 7 9
After copying the value of minNode (7) to the node to be deleted (5). Note that it doesn’t break the property of BST.
7 <--- (node to be deleted)
/ \
3 10
/ \
8 11
/ \
(minNode)-> 7 9
After deleting the minNode:-
7
/ \
3 10
/ \
8 11
\
9
We find the minNode using the function findMinimum.
class TreeNode {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {TreeNode} root
* @param {number} key
* @return {TreeNode}
*/
function deleteKey(root, key) {
if (!root) return null
if (key < root.val) {
root.left = deleteKey(root.left, key)
return root
} else if (key > root.val) {
root.right = deleteKey(root.right, key)
return root
}
// we are here means root has value equal `key`
if (root.left === null) {
return root.right
}
if (root.right === null) {
return root.left
}
const minNode = findMinimum(root.right)
// copy value
root.val = minNode.val
// now delete the minnode the right subtree
root.right = deleteKey(root.right, root.val)
return root
}
function findMinimum(node) {
while(node.left !== null) {
node = node.left
}
return node
}n = number of nodes in the tree
Time complexity- O(n) // in case of skewed tree
Space complexity- O(n) // for recursion in case of skewed tree
Approach II (iterative):
In this approach, we solve the problem using an iterative approach. We also delete the node actually instead of copying the value. We create two additional helper functions:
1. findMinimum:- This function finds the minNode in the right subtree of the given node and returns an array containing the parent of minNode and the minNode itself.
2. deleteRootNode:- This function always deletes the root node of the passed tree and returns the modified tree.
In our main function deleteKey, we iterate over the node. We pinpoint the node to be deleted using the same condition in the previous approach:-
â— If key is lesser, we will delete it in the left subtree,
â— if the key is greater, we will delete it in the right subtree.
But this time, we do it iteratively. We have two variables: curr and parent. After the loop ends, curr will be the node to be deleted, and parent will be the parent of curr (the node to be deleted). If parent is null, it means the root of the tree has a value equal to key. In this case, we will directly call deleteRootNode and return it. Otherwise, we check two conditions:-
â— If curr is the left child of parent, we call deleteRootNode with parent.left (or curr) and overwrite parent.left (we are asking deleteRootNode to delete the root node of the tree passed as argument, that is, parent.left, that is, delete parent.left and return the modified tree).
â— And if curr is the right child of parent, we call deleteRootNode with parent.right (or curr) and overwrite parent.right
â— In the end, we return root.
Now let’s see how deleteRootNode works. In this function, we always need to delete the root node. If root has only one child, we directly return that child. Otherwise, we do a different procedure. First, we find the node with the minimum value in the right subtree of root using findMinimum function. We also find its parent. Let these be minNode and parentOfMinNode. The minNode will not have a left child (if it were so, that left child would have been the minNode. see the previous approach for example). Let us take the following example:
5 <--- (node to be deleted aka root)
/ \
3 10 <- (parentOfMinNode)
/ \
(minNode)-> 8 11
\
9
We perform the following steps:
1. Since we are to delete root, we assign its left-child to be the left child of minNode. The tree becomes:
5 <--- (node to be deleted aka root)
/ \
3 10 <- (parentOfMinNode)
/ \
(minNode)-> 8 11
/ \
3 9
^ (the left sub-tree of root is the left subtree of minNode)
----------------------------------------------------------------------
2. The minNode will take the place of root. So we have to take care of the left and right children of root. We have taken care of the left child of root in the previous step. Now we need to assign the right child of root to the right child of minNode. But minNode already has its right child. To do this, we first take care of the right child of minNode. Since the left child of parentOfMinNode will be overwritten, we assign the right of minNode to the left of parentOfMinNode. Then, we assign the right child of root to the right child of minNode. The tree becomes:
(minNode)-> 8 5 (root is now orphan node)
/ \
3 10 <- (parentOfMinNode)
/ \
9 11
(the right ^^^^^ subtree of minNode is the left subtree of parentOfMinNode)
----------------------------------------------------------------------
3. Then we return minNode effectively deleting the desired node.
class TreeNode {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {TreeNode} root
* @param {number} key
* @return {TreeNode}
*/
function deleteKey(root, key) {
let curr = root
let parent = null
while (curr !== null && curr.val !== key) {
parent = curr
if (key < curr.val) {
curr = curr.left
} else {
curr = curr.right
}
}
// the root node of the given BST
// has value equal to `key`
if (parent === null) {
return deleteRootNode(root)
}
// the node to be deleted is the left child of `parent`
if (parent.left === curr) {
parent.left = deleteRootNode(parent.left)
}
// the node to be deleted is the right child of `parent`
if (parent.right === curr) {
parent.right = deleteRootNode(parent.right)
}
return root
}
function deleteRootNode(root) {
if (!root) return null
if (!root.left) return root.right
if (!root.right) return root.left
const [parentOfMinNode, minNode] = findMinimum(root.right)
minNode.left = root.left
if (root.right !== minNode) {
parentOfMinNode.left = minNode.right
minNode.right = root.right
}
return minNode
}
function findMinimum(node) {
let parent = null
while(node.left !== null) {
parent = node
node = node.left
}
return [parent, node]
}n = number of nodes in the tree
Time complexity- O(n) // in case of skewed tree
Space complexity- O(1)
Advantages:
1. Recursion stack is avoided giving constant time complexity
2. It does not copy values from nodes which we did in the recursive approach. In reality, the node does not contain only integer values. Copying the data in nodes can be a time-consuming task.
Written by S. Kumar on May 22nd, 2021
11. Return all elements in two binary search trees.
This question shows the developer's ability to work with JavaScript binary search and indices.
You are given the root nodes root1 and root2 of two binary search trees (BST). Your task is to return all the integers from both trees in an array in ascending order.
/*Example*/
Given trees:
2 1
/ \ / \
1 4 0 3
Expected output: [0, 1, 1, 2, 3, 4]Solution:
First of all, we find all the nodes in each tree into tree1 and tree2. Since both are binary search trees, we will do inorder over the trees and the resulting array will be already sorted. Next, we will combine both arrays into one sorted array. We will have two pointers (indices) i and j pointing to the arrays tree1 and tree2 respectively. We will have a third pointer k, pointing to the next location in res array where the next larger element will be stored. We will iterate over both the arrays tree1 and tree2, find the next larger element and store it in res array. At last, we return res.
class TreeNode {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {TreeNode} root1
* @param {TreeNode} root2
* @return {number[]}
*/
var getAllElements = function(root1, root2) {
const tree1 = inorderTraversal(root1)
const tree2 = inorderTraversal(root2)
const tree1Count = tree1.length
const tree2Count = tree2.length
const res = new Array(tree1Count + tree2Count)
let i = 0
let j = 0
let k = 0
while (i < tree1Count && j < tree2Count) {
res[k++] = tree1[i] < tree2[j]
? tree1[i++]
: tree2[j++]
}
while(i < tree1Count) {
res[k++] = tree1[i++]
}
while(j < tree2Count) {
res[k++] = tree2[j++]
}
return res
}
function inorderTraversal(root) {
const res = []
function _inorder(node) {
if (node === null) return
_inorder(node.left)
res.push(node.val)
_inorder(node.right)
}
_inorder(root)
return res
}n = number of nodes in tree1
m = number of nodes in tree2
Time complexity- O(n + m)
Space complexity- O(n + m)
Written by S. Kumar on May 22nd, 2021
12. Create a maximum binary tree.
This question focuses on JavaScript elements and recursion.
You are given an integer array nums with no duplicates. Your task is to create a maximum binary tree using:
1. Create a root node with max value in nums
2. Recursively build the left subtree on the subarray prefix to the left of the maximum value
3. Recursively build the right subtree on the subarray prefix to the right of the maximum value
/*Example*/
Given nums = [3, 2, 1, 6, 0, 5]
Expected tree:
6
/ \
3 5
\ /
2 0
\
1Solution:
We will do this recursively. We will create a helper function construct that constructs the maximum binary tree on nums between indices left and right. Thus our required tree will be formed by construct(nums, 0, nums.length - 1). This function finds the index of the maximum element in the subarray using another helper function findMaxIndex. Then create a node with that maximum value and recursively build the left and right subtrees.
class TreeNode {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {number[]} nums
* @return {TreeNode}
*/
function constructMaximumBinaryTree(nums) {
return construct(nums, 0, nums.length - 1)
}
function construct(nums, left, right) {
if (left > right) return null
const maxIndex = findMaxIndex(nums, left, right)
const node = new TreeNode(nums[maxIndex])
node.left = construct(nums, left, maxIndex - 1)
node.right = construct(nums, maxIndex + 1, right)
return node
}
function findMaxIndex(nums, left, right) {
let maxIndex = left
for (let i = left; i <= right; i++) {
if (nums[i] > nums[maxIndex]) {
maxIndex = i
}
}
return maxIndex
}n = length of nums
Time complexity- O(n2)
Space complexity- O(n)
Written by S. Kumar on May 22nd, 2021
13. How do you prune the binary tree?
This question shows the developer's ability to work with JavaScript recursion.
You are given the root node of a binary tree. A node of the tree has a value equal to either 0 or 1. Your task is to remove those subtrees from the tree which have no node with a value equal to 1.
/*Example*/
Given tree:
1
\
0
/ \
0 1
Expected tree:
1
\
0
\
1
Given tree:
1
/ \
0 1
/ \ / \
0 0 0 1
Expected tree:
1
\
1
\
1Solution:
We will remove the nodes recursively. We will do the depth-first search over the whole tree. If the current node is a leaf tree and it has a value equal to 0, we will remove it. To remove a node, we return null to the parent node. If we don’t need to remove the node, we return the node itself.
class TreeNode {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
function pruneTree(root) {
if (!root) return null
root.left = pruneTree(root.left)
root.right = pruneTree(root.right)
const isLeaf = root.left === null && root.right === null
if (isLeaf && root.val === 0) {
return null
}
return root
}n = number of nodes in the tree
Time complexity- O(n)
Space complexity- O(n)
Written by S. Kumar on May 22nd, 2021
14. Distribute coins in the binary tree.
This question focuses on JavaScript traversal.
You are given the root node of a binary tree. The tree contains n nodes. For each node, node.val represents the number of coins that node has. The total number of coins in the tree is equal to the number of nodes, that is, equal to n.
You perform a series of operations on the tree. In one operation, you take one coin from a node and transfer it to one of its adjacent nodes (that is either from parent to child or from child to parent). Your task is to find the minimum number of operations such that each node has exactly one coin.
/*Example*/
Given tree:
3
/ \
0 0
Expected output: 2
Explanation: From the root node, we move one coin to the left child and one coin to the right child. Hence 2 operations.
Given tree:
0
/ \
3 0
Expected output: 3
Explanation: From the left child, we move two coins to the root node (total 2 operations, one for each coin). The resulting tree becomes:-
2
/ \
1 0
Then we move one coin from the root node to the right child. So total 3 operations.Solution:
We will do post-order traversal on the tree. For every node, we will calculate the balance factor. The balance factor for a node is the number of coins is the number of extra coins in its both subtree including the node itself. Consider the following tree, the balance factors are shown in parentheses:
 
0 (0)
/ \
(+1) 0 0 (0)
/ \ / \
(+3) 4 0 3(=2) 0 (-1)
(-1)
If a node has a positive balance factor, it means the node has extra coins it would like to give. If the balance factor is negative, it means the node needs that number of coins such that every node has exactly one coin. Let leftBalance and rightBalance be the balance factors of the left and right children of a node. This node will take/give leftBalance number of coins to/from the left child.
Thus the operationsCount while taking/giving to/from the left child will be increased by leftBalance. The same applies for the right child. The number of operations for a node that will transact coins with its children nodes will be equal to the sum of the absolute values of the balance factors of the children nodes.
class TreeNode {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {TreeNode} root
* @return {number}
*/
function distributeCoins(root) {
let operationsCount = 0
function traverse(root) {
if (!root) return null
const leftBalance = traverse(root.left)
const rightBalance = traverse(root.right)
operationsCount +=
Math.abs(leftBalance) +
Math.abs(rightBalance)
return root.val + leftBalance + rightBalance - 1
}
traverse(root)
return operationsCount
}Time complexity- O(n)
Space complexity- O(n)
Written by S. Kumar on May 22nd, 2021