Count BST subtrees that lie in given range | C ++ program to count subtrees that lie in a given range ; A BST node ; A utility function to check if data of root is in range from low to high ; A recursive function to get count of nodes whose subtree is in range from low to hgih . This function returns true if nodes in subtree rooted under ' root ' are in range . ; Base case ; Recur for left and right subtrees ; If both left and right subtrees are in range and current node is also in range , then increment count and return true ; A wrapper over getCountUtil ( ) . This function initializes count as 0 and calls getCountUtil ( ) ; Utility function to create new node ; Driver program ; Let us construct the BST shown in the above figure ; Let us constructed BST shown in above example 10 / \ 5 50 / / \ 1 40 100
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct node { int data ; struct node * left , * right ; } ; bool inRange ( node * root , int low , int high ) { return root -> data >= low && root -> data <= high ; } bool getCountUtil ( node * root , int low , int high , int * count ) { if ( root == NULL ) return true ; bool l = getCountUtil ( root -> left , low , high , count ) ; bool r = getCountUtil ( root -> right , low , high , count ) ; if ( l && r && inRange ( root , low , high ) ) { ++ * count ; return true ; } return false ; } int getCount ( node * root , int low , int high ) { int count = 0 ; getCountUtil ( root , low , high , & count ) ; return count ; } node * newNode ( int data ) { node * temp = new node ; temp -> data = data ; temp -> left = temp -> right = NULL ; return ( temp ) ; } int main ( ) { node * root = newNode ( 10 ) ; root -> left = newNode ( 5 ) ; root -> right = newNode ( 50 ) ; root -> left -> left = newNode ( 1 ) ; root -> right -> left = newNode ( 40 ) ; root -> right -> right = newNode ( 100 ) ; int l = 5 ; int h = 45 ; cout << " Count ▁ of ▁ subtrees ▁ in ▁ [ " << l << " , ▁ " << h << " ] ▁ is ▁ " << getCount ( root , l , h ) ; return 0 ; }