How to Answer: What is the range sum of BST?
Advice and answer examples written specifically for a Java Beginner Level Tree job interview.
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