# Count BST nodes that lie in a given range

Given a Binary Search Tree (BST) and a range l-h(inclusive), count the number of nodes in the BST that lie in the given range.

- The values smaller than root go to the left side
- The values greater and equal to the root go to the right side

Example 1:

```
Input:
10
/ \
5 50
/ / \
1 40 100
l = 5, h = 45
Output: 3
Explanation: 5 10 40 are the node in the
range
```

Example 2:

```
Input:
5
/ \
4 6
/ \
3 7
l = 2, h = 8
Output: 5
Explanation: All the nodes are in the
given range.
```

**method :**

**c++ implementation:**

vector<int>v; void printInorder(struct Node* node) { if (node == NULL) return; printInorder(node->left); v.push_back(node->data); printInorder(node->right); } int getCount(Node *root, int l, int h) { int c=0; while(!v.empty()) v.pop_back(); vector<int>::iterator i; printInorder(root); for(i=v.begin();i!=v.end();i++) { if(l<=*i && *i<=h) c++; } return c; }

**Time Complexity:**O(n)

**space Complexity:**O(n)

n is the height of tree.