The challenge for today is how to determine the specified range sum of BST, but before that let’s recap what exactly is BST?
BST stands for binary search tree. Before we go into the methods, let's review what a tree data structure is in programming and what BST refers to.
A tree is a data structure made up of nodes that have the following properties:
Each tree contains a root node (at the top) having some value.
There are zero or more child nodes under the root node.
Each child node has one or more children, and so forth. This results in the formation of a subtree in the tree. Every node has its subtree, which is made up of his children and their children, and so on. This means that every node can be a tree on its own.
What is a binary search tree?
The BST is based on the binary search algorithm, which provides rapid node lookup, insertion, and removal. Because of the way they are put up, each comparison enables the operations to skip approximately half of the tree on average; thus, each search, insertion, or deletion takes time proportional to the logarithm of the number of items kept in the tree, O(log n).
What are the characteristics of a binary search tree?
A binary search tree (BST) encompasses four primary characteristics:
Each node can have a maximum of two children.
The left subtree of a node contains only nodes with keys lower than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Each left and right subtree must be a binary search tree.
Now that you've reviewed the tree data structure and the binary search tree, it's time to put our heads together to solve an intriguing problem based on BST.
The problem says: Given the root node of a BST and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].
Example 1:
Tree:- [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation:- Nodes 7, 10, and 15 are in the range [7, 15].
The idea is straightforward, execute a recursive Depth-first Searchand add the node value to the answer whenever the root value meets the provided range.
Now let’s discuss the Algorithm for the same:
Algorithm
Step 1: Initialize a variable 'sum' to 0, which will be used to hold the final answer.
Step 2: Define a recursive function RangeSumBST that accepts three arguments: 'root,' 'low,' and 'high,' denoting the provided root node of the binary tree, the lowest range value, and the highest value of the range, respectively.
Step 2.1: Edge case- When the root is null, the function should return the sum to the corresponding function call since a NULL value signals no further nodes to visit on that subtree.
Initially, if the root itself is null, then the pointer will return from the program.
Step 2.2: If the current node's value is greater than 'low' and less than 'high,' add the current node's value to 'sum.’
Invoke the recursive function for the left child of the current node.
Invoke the recursive function for the right child of the current node.
Step 2.3: If the above condition fails, i.e., when the current node’s become less than 'low,’ then call the recursive function for the right node of the current node, and if the current node’s value is greater than 'high,’ then call the recursive function for the left node of the current node.
Step 3: Return ans. Below is the Pseudocode you can refer to implement the code. 😛
Pseudo Code
Initialize a variable ans = 0
int rangeSumBST(node* root, int low, int high)
if(root == NULL)
return sum
if(root->val>=low && root->val<=high)
sum+=root->val
rangeSumBST(root->left,low,high)
rangeSumBST(root->right,low,high)
else if (root->val < low)
rangeSumBST(root->right,low,high)
else
rangeSumBST(root->left,low,high)
return sum
Now let’s have a look at the Implementation part of the Range Sum of BST :
Implementations
C++
Java
Python
Javascript
C#
C++
// C++ program to calculate the range sum of BST nodes within a given range
#include<bits/stdc++.h>
using namespace std;
// A BST node
struct node
{ int val;
struct node* left, *right;
};
// Utility function to create a new node
node *newNode(int val)
{
node *temp = new node;
temp->val = val;
temp->left = temp->right = NULL;
return (temp);
}
// Returns the sum of nodes in BST in the range [low, high]
int sum =0;
// Recursive function to traverse the nodes
int rangeSumBST(node* root, int low, int high)
{
// If the current node has null in its value, then return to the corresponding function call
if(root == NULL)
{
return sum;
}
// If the current node's value lies in the given range, then add its value to the sum variable.
if(root->val>=low && root->val<=high)
{
sum += root->val;
// Call its left subtree recursively
rangeSumBST(root->left,low,high);
// Call its right subtree recursively
rangeSumBST(root->right,low,high);
}
// If the current node's value is less than the low, call its right subtree recursively.
else if (root->val < low)
{
rangeSumBST(root->right,low,high);
}
// If the current node's value is greater than the high, call its left subtree recursively.
else
{
rangeSumBST(root->left,low,high);
}
return sum;
}
int main()
{
/* Let us constructed BST shown in the above example-1
10
/ \
5 15
/ \ \
4 7 18 */
node *root = newNode(10);
root->left = newNode(5);
root->right = newNode(15);
root->left->left = newNode(4);
root->left->right = newNode(7);
root->right->right = newNode(100);
int low, high;
cout<<"Enter the starting value of the range: "<<endl;
cin>>low;
cout<<"Enter the ending value of the range: "<<endl;
cin>>high;
// function call
cout << "Range sum of BST between [" << low << ", " << high
<< "] is " << rangeSumBST(root, low, high);
return 0;
}
Java
// Java program to calculate the range sum of BST nodes within a given range
class TreeNode { int val; TreeNode left, right;
TreeNode(int item) { val = item; left = right = null; } }
public class RangeSumBST { // Recursive function to traverse the nodes public static int rangeSumBST(TreeNode root, int low, int high) { if (root == null) return 0; if (root.val >= low && root.val <= high) return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high); else if (root.val < low) return rangeSumBST(root.right, low, high); else return rangeSumBST(root.left, low, high); }
public static void main(String[] args) { /* Let us construct BST shown in the above example 10 / \ 5 15 / \ \ 4 7 100 */ TreeNode root = new TreeNode(10); root.left = new TreeNode(5); root.right = new TreeNode(15); root.left.left = new TreeNode(4); root.left.right = new TreeNode(7); root.right.right = new TreeNode(100);
int low = 7, high = 15;
// Function call System.out.println("Range sum of BST between [" + low + ", " + high + "] is " + rangeSumBST(root, low, high)); } }
Python
# Python program to calculate the range sum of BST nodes within a given range
class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None
# Recursive function to traverse the nodes def range_sum_BST(root, low, high): if not root: return 0 if low <= root.val <= high: return root.val + range_sum_BST(root.left, low, high) + range_sum_BST(root.right, low, high) elif root.val < low: return range_sum_BST(root.right, low, high) else: return range_sum_BST(root.left, low, high)
# Let us construct BST shown in the above example # 10 # / \ # 5 15 # / \ \ # 4 7 100 root = TreeNode(10) root.left = TreeNode(5) root.right = TreeNode(15) root.left.left = TreeNode(4) root.left.right = TreeNode(7) root.right.right = TreeNode(100)
low, high = 7, 15
# Function call print("Range sum of BST between [", low, ",", high, "] is", range_sum_BST(root, low, high))
Javascript
// JavaScript program to calculate the range sum of BST nodes within a given range
// Recursive function to traverse the nodes function rangeSumBST(root, low, high) { if (!root) return 0; if (root.val >= low && root.val <= high) return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high); else if (root.val < low) return rangeSumBST(root.right, low, high); else return rangeSumBST(root.left, low, high); }
// Let us construct BST shown in the above example // 10 // / \ // 5 15 // / \ \ // 4 7 100 let root = new TreeNode(10); root.left = new TreeNode(5); root.right = new TreeNode(15); root.left.left = new TreeNode(4); root.left.right = new TreeNode(7); root.right.right = new TreeNode(100);
let low = 7, high = 15;
// Function call console.log("Range sum of BST between [" + low + ", " + high + "] is " + rangeSumBST(root, low, high));
C#
// C# program to calculate the range sum of BST nodes within a given range
using System;
public class TreeNode { public int val; public TreeNode left, right;
public TreeNode(int item) { val = item; left = right = null; } }
public class RangeSumBST { // Recursive function to traverse the nodes public static int RangeSumBST(TreeNode root, int low, int high) { if (root == null) return 0; if (root.val >= low && root.val <= high) return root.val + RangeSumBST(root.left, low, high) + RangeSumBST(root.right, low, high); else if (root.val < low) return RangeSumBST(root.right, low, high); else return RangeSumBST(root.left, low, high); }
public static void Main(string[] args) { /* Let us construct BST shown in the above example 10 / \ 5 15 / \ \ 4 7 100 */ TreeNode root = new TreeNode(10); root.left = new TreeNode(5); root.right = new TreeNode(15); root.left.left = new TreeNode(4); root.left.right = new TreeNode(7); root.right.right = new TreeNode(100);
int low = 7, high = 15;
// Function call Console.WriteLine("Range sum of BST between [" + low + ", " + high + "] is " + RangeSumBST(root, low, high)); } }
Input Test Case-1
Enter the starting value of the range :
7
Enter the ending value of the range :
15
Output
Range sum of BST between [7, 15] is 32
Explanation:- Nodes 7, 10, and 15 are in the range [7, 15].
7 + 10 + 15 = 32.
Input Test Case-2
Enter the starting value of the range :
4
Enter the ending value of the range :
10
Output
Range sum of BST between [4, 10] is 26
Explanation:- Nodes 4, 5, 7, and 10 are in the range [4, 10].
4 + 5 + 7 + 10 = 26.
Complexity Analysis
Time Complexity: O(n), where n is the total number of nodes in the BST.
Auxiliary Space: O(h), where h is the height of the BST. In the worst case, the BST can be skewed and the space consumed due to recursive call stack can go upto n, where n is the the number of nodes in the BST.
We begin by looking at the root node. If the tree is null, it means that the key we're looking for does not exist in the tree. Otherwise, the key is compared to the root node; if they match, the node is returned; check for its left subtree if key < root, and check recursively for the left subtree. If that is not the case, look for the right subtree by using if key > root and then search for the right subtree recursively.
What is the degree in a binary tree?
The degree of a binary tree is the total number of nodes that it has as offspring, i.e., the total number of nodes that originate from it. Because the tree's leaf has no children, its degree is zero. The number of partitions in the subtree with that node as the root determines a node's degree.
What is the range sum of BST?
The range sum of BST or any other tree is nothing but the sum between the provided intervals.
Conclusion
To conclude the talk, we emphasized one programming question, i.e., the Range sum of BST. The only recommendation is to solve as many problems as possible since this will lead to you becoming an expert problem solver. The problem becomes simple and easy to grasp when you break the question down into its constituent pieces. Continue to try similar queries to improve yourself.
Don't stop here, Ninja; check out our other fantastic articles that can help you handle a variety of common difficulties.
38+ registered 