BST queries

PROBLEM STATEMENT

You are given an arbitrary binary search tree (BST) with N nodes numbered 1 to N, and each node is associated with a value. You are also given Q queries, each of the Q queries are of the form [ L, R ], your task is to find the number of nodes in the BST which lie in the range L to R for each query.

For example

You are given the following tree.

altImage

And you are given 3 queries as follows
Q1 = [ 2 , 12 ]
Q2 = [ 10 , 50 ]
Q3 = [ 14 , 20 ] 

Then the answers for them will be as follows.
Answer for Q1 = 3 i.e. nodes 5, 10 , 12.
Answer for Q2 = 6 i.e. nodes 10 , 12 , 15 , 19 , 20 , 28.
Answer for Q3 = 3 i.e. nodes 15 , 19 , 20.

Note :

It is guaranteed that the tree given will be a binary search tree.
It is guaranteed that all the node values will be distinct.

Input Format:

The first line of the input contains a single positive integer T, denoting the number of test cases.

The first line of each test case contains two positive integers N and Q, denoting the number of nodes in the BST and the number of queries respectively.

The second line contains the values of the nodes of the tree in the level order form ( 0 for NULL node) Refer to the example for further clarification.

The next Q lines of each test case contain two positive integers L and R as described in the problem statement.

Example: Consider the binary tree

altImage

The input of the tree depicted in the image above will be like: 

4
3 6
1 0 5 7
0 2 0 0 0 0
0 0

Explanation :
    7 is the number of nodes
    The second line contains the value of nodes from 1 to 7.
    Then the structure of the tree follows. 
Level 1 :
    The root node of the tree is 4

Level 2 :
    Left child of 4 = 3
    Right child of 4 = 6

Level 3 :
    Left child of 3 = 1
    Right child of 3 = null (0)
    Left child of 6 = 5
    Right child of 6 = 7

Level 4 :
    Left child of 1 = null (0)
    Right child of 1 = 2
    Left child of 5 = null (0)
    Right child of 5 = null (0)
    Left child of 7 = null (0)
    Right child of 7 = null (0)

Level 5 :
    Left child of 2 = null (0)
    Right child of 2 = null (0)

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 (0).

Output Format:

For each query print a single integer on a new line, denoting the number of nodes in the tree with a value between L and R.

Note:

You don't have to print anything, it has already been taken care of. Just Implement the given function.

Constraints:

1 <= T <= 50
1 <= N, Q <= 3000
1 <= Value in a node <= 10^9 
1  <= L <= R <= 10^9
Time Limit : 1 sec

Approach 1

The idea is to traverse all the nodes using preorder traversal and count the number of nodes which are in the given range.
We will initialize the variable Count with zero which we will use to keep count of all the nodes in the given range.
We will start the preorder traversal from the root node and repeat the following until we reach the null node.
- If the current node is in the given range then we increase the Count by one.
- Then we will call the preorder traversal of the left child and then right child.
We will return Count as answer.
For example given the following tree.

And the query is [ 2 , 9 ] .
- We will initialize Count = 0 , call the preorder traversal of 5.
  - In preorder traversal of 5 we increase count by 1 as 2 <= 5 <= 9.
  - We call the preorder traversal of 3.
    - In preorder traversal of 3 the count remains unchanged.
    - Going back to 5.
  - We call the preorder traversal of 8.
    - In preorder traversal of 8 the count is increase by 1 ase 2 <= 8 <= 9.
    - We return back to 5.
  - We return back.
- We return the count as the answer which is 2.

Try Problem

Approach 2

The idea is to traverse the tree only once and generate the inorder traversal vector which will be a sorted vector as the inorder traversal is sorted.
Declare the answer vector where we will store the answers of all the queries.
Traverse the tree and generate its inorder traversal vector.
Now we will traverse through Q queries and we will store the answer of each query in the answer vector.
- Using binary search we can find the position of any value in the sorted vector in logn. We know that the inorder vector will be sorted.
- Let's say we have a query [ L , R ] and we want to find the number of values in the inorder vector. Here L is the lower limit of the query and R is the upper limit of the query.
- We will find the index of the element just greater than the upper limit and we will call it IndexR. We can do this using binary search in logN time.
- We will find the Index of the element just greater than or equal to the lower limit and we will call it IndexL. We can do this using binary search in logN time.
  - Let’s say we have inorder vector with following values
    - [ 2, 4, 5, 6, 19]
  - And we have a query [ 3 , 10]
  - Then IndexL will be 4 and IndexR will be 1
- All the elements from IndexL to IndexR will be in range L to R so we will return the count of elements between this index which would be equal to IndexR - IndexL.
  - In the above query it would be 4 - 1 i.e. 3.
- So for each query we will push (IndexR - IndexL) in our answer vector.
Return the answer vector.