Sum of nodes in a Binary Search Tree with values from a given range | Java 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
import java . util . * ; class GFG { static class Node { int val ; Node left , right ; } ; static Node newNode ( int item ) { Node temp = new Node ( ) ; temp . val = item ; temp . left = temp . right = null ; return temp ; } static int sum = 0 ; static int rangeSumBST ( Node root , int low , int high ) { if ( root == null ) return 0 ; Queue < Node > q = new LinkedList < Node > ( ) ; q . add ( root ) ; while ( q . isEmpty ( ) == false ) { Node curr = q . peek ( ) ; q . remove ( ) ; if ( curr . val >= low && curr . val <= high ) { sum += curr . val ; } if ( curr . left != null && curr . val > low ) q . add ( curr . left ) ; if ( curr . right != null && curr . val < high ) q . add ( curr . right ) ; } return sum ; } static 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 ; } public static void main ( String [ ] args ) { 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 ; System . out . print ( rangeSumBST ( root , L , R ) ) ; } }