Sum of nodes in a Binary Search Tree with values from a given range | Class for node of the Tree ; Function to create a new BST 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 ; Let us create following BST 10 / \ 5 15 / \ \ 3 7 18
class Node { constructor ( item ) { this . val = item ; this . left = this . right = null ; } } let sum = 0 ; function rangeSumBST ( root , low , high ) { if ( root == null ) return 0 ; let q = [ ] ; q . push ( root ) ; while ( q . length != 0 ) { let curr = q . shift ( ) ; 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 ; } function insert ( node , data ) { if ( node == null ) return new Node ( data ) ; if ( data <= node . val ) node . left = insert ( node . left , data ) ; else node . right = insert ( node . right , data ) ; return node ; } let root = null ; root = insert ( root , 10 ) ; insert ( root , 5 ) ; insert ( root , 15 ) ; insert ( root , 3 ) ; insert ( root , 7 ) ; insert ( root , 18 ) ; let L = 7 , R = 15 ; document . write ( rangeSumBST ( root , L , R ) ) ;