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.