2 Java Beginner Level Tree Interview Questions & Answers
Below is a list of our Java 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 concentrates on the developer's skills working with Java binary trees and iteration.
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.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public TreeNode removeLeafNodes(TreeNode root, int target) {
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 skills working with Java traverse and binary tree search.
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.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public int rangeSumBST(TreeNode root, int low, int high) {
if (root == null) return 0;
int 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.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public int rangeSumBST(TreeNode root, int low, int high) {
if (root == null) return 0;
int 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