1.
Introduction
2.
What is a binary search tree?
3.
What are the characteristics of a binary search tree?
3.1.
Example 1:
3.2.
Example 2:
4.
Method 1: Recursive approach
4.1.
Algorithm
4.2.
Pseudo Code
4.3.
Implementations
4.4.
C++
4.5.
Java
4.6.
Python
4.7.
Javascript
4.8.
C#
4.9.
Input Test Case-1
4.10.
Input Test Case-2
4.11.
Complexity Analysis
5.
5.1.
How to search a node in a binary tree?
5.2.
What is the degree in a binary tree?
5.3.
What is the range sum of BST?
6.
Conclusion
Last Updated: Apr 29, 2024
Medium

# Range Sum of BST

## Introduction

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.

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].

7 + 10 + 15 = 32.

### Example 2:

Tree: = [11, 7, 15, 5, 9, 12, 20, 3, null,  8, null], low = 8, high = 15

Output: 55

Explanation:- Nodes 8, 9, 11, 12 and 15 are in the range [8, 15].

8 + 9 + 11 + 12 + 15 = 55.

Before moving to the solution, try to Implement it on your own first.

## Method 1: Recursive approach

The idea is straightforward, execute a recursive Depth-first Search and 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 :

• 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 nodestruct node{   int val;    struct node* left, *right;};// Utility function to create a new nodenode *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 nodesint 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 rangeclass 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 rangeclass TreeNode:    def __init__(self, val):        self.val = val        self.left = None        self.right = None# Recursive function to traverse the nodesdef 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       100root = 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 callprint("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 rangeclass TreeNode {    constructor(val) {        this.val = val;        this.left = null;        this.right = null;    }}// Recursive function to traverse the nodesfunction 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       100let 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 callconsole.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 rangeusing 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.

### How to search a node in a binary tree?

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.