Sum of nodes in a Binary Search Tree with values from a given range | C ++ program for the above approach ; Class for node of the Tree ; Function to create a new BST node ; Return the newly created node ; Stores the sum of all nodes lying in the range [ L , R ] ; Function to perform level order traversal on the Tree and calculate the required sum ; Base Case ; Stores the nodes while performing level order traversal ; Push the root node into the queue ; Iterate until queue is empty ; Stores the front node of the queue ; If the value of the node lies in the given range ; Add it to sum ; If the left child is not NULL and exceeds low ; Insert into queue ; If the right child is not NULL and exceeds low ; Insert into queue ; Return the resultant sum ; Function to insert a new node into the Binary Search Tree ; Base Case ; If the data is less than the value of the current node ; Recur for left subtree ; Otherwise ; Recur for the right subtree ; Return the node ; Driver Code ; Let us create following BST 10 / \ 5 15 / \ \ 3 7 18
#include <bits/stdc++.h> NEW_LINE using namespace std ; class Node { public : int val ; Node * left , * right ; } ; Node * newNode ( int item ) { Node * temp = new Node ( ) ; temp -> val = item ; temp -> left = temp -> right = NULL ; return temp ; } int sum = 0 ; int rangeSumBST ( Node * root , int low , int high ) { if ( root == NULL ) return 0 ; queue < Node * > q ; q . push ( root ) ; while ( q . empty ( ) == false ) { Node * curr = q . front ( ) ; q . pop ( ) ; if ( curr -> val >= low && curr -> val <= high ) { sum += curr -> val ; } if ( curr -> left != NULL && curr -> val > low ) q . push ( curr -> left ) ; if ( curr -> right != NULL && curr -> val < high ) q . push ( curr -> right ) ; } return sum ; } Node * insert ( Node * node , int data ) { if ( node == NULL ) return newNode ( data ) ; if ( data <= node -> val ) node -> left = insert ( node -> left , data ) ; else node -> right = insert ( node -> right , data ) ; return node ; } int main ( ) { Node * root = NULL ; root = insert ( root , 10 ) ; insert ( root , 5 ) ; insert ( root , 15 ) ; insert ( root , 3 ) ; insert ( root , 7 ) ; insert ( root , 18 ) ; int L = 7 , R = 15 ; cout << rangeSumBST ( root , L , R ) ; return 0 ; }