Count BST subtrees that lie in given range | 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 high . 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 Code ; Let us construct the BST shown in the above figure ; Let us constructed BST shown in above example 10 / \ 5 50 / / \ 1 40 100
def inRange ( root , low , high ) : NEW_LINE INDENT return root . data >= low and root . data <= high NEW_LINE DEDENT def getCountUtil ( root , low , high , count ) : NEW_LINE INDENT if root == None : NEW_LINE INDENT return True NEW_LINE DEDENT l = getCountUtil ( root . left , low , high , count ) NEW_LINE r = getCountUtil ( root . right , low , high , count ) NEW_LINE if l and r and inRange ( root , low , high ) : NEW_LINE INDENT count [ 0 ] += 1 NEW_LINE return True NEW_LINE DEDENT return False NEW_LINE DEDENT def getCount ( root , low , high ) : NEW_LINE INDENT count = [ 0 ] NEW_LINE getCountUtil ( root , low , high , count ) NEW_LINE return count NEW_LINE DEDENT class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 10 ) NEW_LINE root . left = newNode ( 5 ) NEW_LINE root . right = newNode ( 50 ) NEW_LINE root . left . left = newNode ( 1 ) NEW_LINE root . right . left = newNode ( 40 ) NEW_LINE root . right . right = newNode ( 100 ) NEW_LINE l = 5 NEW_LINE h = 45 NEW_LINE print ( " Count ▁ of ▁ subtrees ▁ in ▁ [ " , l , " , ▁ " , h , " ] ▁ is ▁ " , getCount ( root , l , h ) ) NEW_LINE DEDENT