Last Updated: 16 Mar, 2021

Range Sum of BST

Easy

Asked in companies

Solve now

Problem statement

You are given a Binary Search Tree with its root node and a range. Your task is to find the sum of all the values of the nodes whose values lie in the given range(L, R) inclusive.

A Binary Search tree is a tree in which all the nodes follow the following properties:

1. The value of a node of the left sub-tree is less than the value of the node.

2. The value of a node of the right sub-tree is greater than or equal to the value of the node.

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of every test case contains two integers 'L' and 'R', denoting the range.

The second line of each test case contains elements in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image will be:

alt text

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null(-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output Format:

For each test case, print a single line containing a single integer denoting the sum of all the values of all nodes with a value in the given range.

The output of each test case will be printed in a new line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
0 <= L <= R <= 10 ^ 5
1 <= N <= 10 ^ 4
1<= DATA <=10 ^ 5 and DATA != -1

Where ‘T’ is the number of test cases, ‘L’ is the starting value of the Range, ‘R’ is the ending value of the Range,  and ‘N’ is the total number of nodes in the binary tree, and “DATA” is the value of the binary tree node

Time Limit: 1 sec.

Solve now

Approaches

01 Approach

The idea is to perform a recursive Inorder traversal and whenever the root value satisfies the given range, then add the node value to the answer.

The steps are as follows:

Initialize a variable ‘answer’ to 0, which stores the final answer.
Define a recursive function InOrderTravesral which takes arguments ‘root’, ‘answer’, ‘low’, ‘high’, which denotes the given root node of the binary tree, the final answer, the lowest value of the range, and the highest value of the range respectively.
- Base Condition is when the root is null, then return from the function as it is a NULL value.
- If the value of the current node is greater than ‘low’ and smaller than ‘high’, then add the value of the current node in ‘answer’.
- Call the recursive function for the left node of the current node.
- Call the recursive function for the right node of the current node.
Return the answer.

Solve now

02 Approach

The idea is to use the property of the binary search tree ie. when we reach a node:

if its value is greater than low, then only we will call for the left child. Otherwise, we will neglect that.
if its value is smaller than high, then only we will call for the right child. Otherwise, we will neglect that.

The steps are as follows:

Initialize a variable ‘answer’ to 0, which stores the final answer.
Define a recursive function InOrderTravesral which takes arguments ‘root’, ‘answer’, ‘low’, ‘high’, which denotes the given root node of the binary tree, the final answer, the lowest value of the range, and the highest value of the range respectively.
- Base Condition is when the root is null, then return from the function as it is a NULL value.
- If the value of the current node is greater than ‘low’ and smaller than ‘high’, then add the value of the current node in ‘answer’.
- If the value of the current node is greater than low, then call the recursive function for the left child of the current node.
- If the value of the current node is smaller than high, then call the recursive function for the right child of the current node.
Return the answer.

Solve now