Range Sum of BST

Easy
0/40
Average time to solve is 20m
profile
Contributed by
2 upvotes
Asked in companies
OlaApple

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.

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
18 24
24 15 33 12 21 30 36 9 -1 18 -1 27 -1 -1 -1 -1 -1 -1 -1 -1 -1 
19 21
15 9 21 7 13 19 23 5 -1 11 -1 17 -1 -1 -1 -1 -1 -1 -1 -1 -1
Sample Output 1:
63
40
Explanation for Sample Input 1:
In the first test case, The value of the nodes are 24, 15, 33, 12, 21, 30, 36, 9, 18, and 27 and the values which lie in the range of [18, 24] are 18, 21, and 24. So, the answer is 63.

In the second test case, The value of the nodes are 15, 9, 21, 7, 13, 19, 23, 5, 11, and 17 and the values which lie in the range of [19, 21] are 21, and 19. So, the answer is 40.
Sample Input 2:
2
21 23
15 9 21 7 13 19 23 5 -1 11 -1 17 -1 -1 -1 -1 -1 -1 -1 -1 -1
31 37
25 16 34 13 22 31 37  -1 -1 -1 -1 -1 -1 -1 -1
Sample Output 2:
44
102
Hint

 If we do an Inorder traversal, Can we add the node values to the final answer as per the given condition?

Approaches (2)
Inorder Traversal

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.

 

Time Complexity

O(N), where N is the total number of nodes in the given binary search tree.

 

As we are visiting every node exactly once. Hence, the time complexity is O(N).

Space Complexity

O(N), where N is the total number of nodes in the given binary search tree.

 

As we are having a function calling stack that stores at most all the nodes of the binary search tree.

Code Solution
(100% EXP penalty)
Range Sum of BST
Full screen
Console