Count BST nodes that lie in a given range

Given a Binary Search Tree (BST) and a range, count the number of nodes in the BST that lie in the given range. You are required to complete the function getCountOfNode. You should not read any input from stdin/console. There are multiple test cases. For each test case, this method will be called individually.

Input (only to be used for Expected Output):

The first line of the input contains an integer 'T' denoting the nummber of test cases. Then 'T' test cases follow. Each test case consists of three lines. Description of test cases is as follows:
The First line of each test case contains an integer 'N' which denotes the no of nodes in the BST. .
The Second line of each test case contains 'N' space separated values of the nodes in the BST.
The Third line of each test case contains two space separated integers 'l' and 'h' denoting the range, where l < h

Output:

You are required to complete the function getCountOfNode which takes three arguments. The first being the root of the tree, and then two integers l and h, denoting the range. The function returns an integer denoting the no of nodes in the given range.

Constraints:

1 <= T <= 50
1 <= N <= 50
1 <= l < h < 1000

Example:

Input

1
6
10 5 50 1 40 100
5 45

Output

For More Examples Use Expected Output

Solution :

For solving this question we have to know the concept of BST.

If we know the concept of the BST well than we can solve this questuon easily .

Simple method : If we have no restrication for using memory or traverse any number time in out tree .

So in that case inorder traverse help us .. so we know that in Inorder traverse always give sorted array of element .

So we traverse the tree using Inorder and store the tree in array than we go to perticular range and count the number and return the result. So simple.

Second Method: In this case we traver only one time just send one extra variable which take care of count and each node of tree go through this l<=tree->data<=h and count the data and finally return this extra variable. Check the working code :

Working Code

Count BST nodes that lie in a given range