2 Javascript Beginner Level Tree Interview Questions & Answers
Below is a list of our Javascript Beginner 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. How do you delete leaves with a given value?
This interview question works with JavaScript functions and binary trees.
You are given a root of a binary tree and value target. Your task is to remove all the leaf nodes from the tree with a value equal to the target. One thing to note here is that if you delete a leaf node with the value target and its parent becomes a leaf node with the value target, the parent should also be removed.
/*Example*/
Consider the following tree with target = 2,
1
/ \
2 3
/ / \
2 2 4
After deleting all the leaf nodes with value = 2, the resultant tree becomes-
1
\
3
\
4
Constraints: The given binary tree has between 1 and 3000 nodes.Solution:
To do the job, we need to check if a node is a leaf node and it has a value equal to the target. So we need to iterate over all the nodes. If we look carefully, the parent of some nodes should be checked after its children have been checked (that is a post-order traversal). This is because when both the children of the parent are deleted, the parent becomes a leaf and it has to be removed as well if its value is equal to the target.
class TreeNode {
constructor(val, left, right) {
this.val = val || 0
this.left = left || null
this.right = right || null
}
}
/**
* @param {TreeNode} root
* @param {number} target
* @return {TreeNode}
*/
function removeLeafNodes(root, target) {
// base case
if (root === null) return null
// null is returned if this node need to be removed
root.left = removeLeafNodes(root.left, target)
root.right = removeLeafNodes(root.right, target)
// it is leaf with value equal to target,
// remove it, that is return null. We set the returned
// value to parent's left or right
if (
root.left === null &&
root.right === null &&
root.val === target
) return null
return root
};Time complexity - O(n) // n is the total number of nodes
Space complexity - O(height of tree)
Written by Jennie Taylor on May 21st, 2021
2. What is the range sum of BST?
This interview question concentrates on the developer's knowledge of JavaScript binary search trees.
You are given the root node of a binary search tree and two integers low and high. Your task is to find the sum of all nodes in the BST which have their values between low and high.
/*Example*/
Given BST-
10
/ \
5 15
/ \ \
3 7 28
low = 7
high = 15
expected output = 32 // (sum of 7, 10, 15)Solution:
We can traverse over each node of the tree and check if it is in the range. If it is the range, add its value to the result, if not, discard it and iterate over its children. We can use either DFS or BFS to traverse the tree.
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 findRangeSum(root, low, high) {
if (root === null) return 0
let result = 0
if (root.val >= low && root.val <= high) {
result += root.val
}
result += rangeSumBST(root.left, low, high)
result += rangeSumBST(root.right, low, high)
return result
}Time complexity- O(no of nodes)
Space complexity- O(height of tree)
There is one optimization. If the value of a certain node is less than or equal to the low, we need not traverse its left subtree. In the above example, for the node with value 5 which is less than low = 7, we need to traverse its left subtree.
The same is true for high. If the value of a certain node is greater than or equal to the high, we need not traverse its right subtree. In the above example, for the node with value 15 which is greater than or equal to high = 15, we need to traverse its right subtree.
class Node {
constructor(val, left, right) {
this.val = val || 0
this.left = left || 0
this.right = right || 0
}
}
/**
* @param {Node} root
* @param {number} low
* @param {high} low
* @return {number}
*/
function findRangeSum(root, low, high) {
if (root === null) return 0
let result = 0
if (root.val >= low && root.val <= high) {
result += root.val
}
if (root.val > low) {
result += rangeSumBST(root.left, low, high)
}
if (root.val < high) {
result += rangeSumBST(root.right, low, high)
}
return result
}Time complexity- O(no of nodes)
Space complexity- O(height of tree)
Written by Jennie Taylor on May 21st, 2021