Sum of nodes in a Binary Search Tree with values from a given range
Given a Binary Search Tree consisting of N nodes and two positive integers L and R, the task is to find the sum of values of all the nodes that lie in the range [L, R].
Examples:
Input: L = 7, R = 15
10
/ \
5 15
/ \ \
3 7 18
Output: 32
Explanation:
The nodes in the given Tree that lies in the range [7, 15] are {7, 10, 15}. Therefore, the sum of nodes is 7 + 10 + 15 = 32.Input: L = 11, R = 15
8
/ \
5 11
/ \ \
3 6 20
Output: 11
Approach: The given problem can be solved by performing any Tree Traversal and calculating the sum of nodes which are lying in the range [L, R].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Class for node of the Tree class Node { public : int val; Node *left, *right; }; // Function to create a new BST node Node* newNode( int item) { Node* temp = new Node(); temp->val = item; temp->left = temp->right = NULL; // Return the newly created node return temp; } // Stores the sum of all nodes // lying in the range [L, R] int sum = 0; // Function to perform level order // traversal on the Tree and // calculate the required sum int rangeSumBST(Node* root, int low, int high) { // Base Case if (root == NULL) return 0; // Stores the nodes while // performing level order traversal queue<Node*> q; // Push the root node // into the queue q.push(root); // Iterate until queue is empty while (q.empty() == false ) { // Stores the front // node of the queue Node* curr = q.front(); q.pop(); // If the value of the node // lies in the given range if (curr->val >= low && curr->val <= high) { // Add it to sum sum += curr->val; } // If the left child is // not NULL and exceeds low if (curr->left != NULL && curr->val > low) // Insert into queue q.push(curr->left); // If the right child is not // NULL and exceeds low if (curr->right != NULL && curr->val < high) // Insert into queue q.push(curr->right); } // Return the resultant sum return sum; } // Function to insert a new node // into the Binary Search Tree Node* insert(Node* node, int data) { // Base Case if (node == NULL) return newNode(data); // If the data is less than the // value of the current node if (data <= node->val) // Recur for left subtree node->left = insert(node->left, data); // Otherwise else // Recur for the right subtree node->right = insert(node->right, data); // Return the node return node; } // Driver Code int main() { /* Let us create following BST 10 / \ 5 15 / \ \ 3 7 18 */ 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; } |
Java
// Java program for the above approach import java.util.*; public class GFG{ // Class for node of the Tree static class Node { int val; Node left, right; }; // Function to create a new BST node static Node newNode( int item) { Node temp = new Node(); temp.val = item; temp.left = temp.right = null ; // Return the newly created node return temp; } // Stores the sum of all nodes // lying in the range [L, R] static int sum = 0 ; // Function to perform level order // traversal on the Tree and // calculate the required sum static int rangeSumBST(Node root, int low, int high) { // Base Case if (root == null ) return 0 ; // Stores the nodes while // performing level order traversal Queue<Node> q = new LinkedList<Node>(); // Push the root node // into the queue q.add(root); // Iterate until queue is empty while (q.isEmpty() == false ) { // Stores the front // node of the queue Node curr = q.peek(); q.remove(); // If the value of the node // lies in the given range if (curr.val >= low && curr.val <= high) { // Add it to sum sum += curr.val; } // If the left child is // not null and exceeds low if (curr.left != null && curr.val > low) // Insert into queue q.add(curr.left); // If the right child is not // null and exceeds low if (curr.right != null && curr.val < high) // Insert into queue q.add(curr.right); } // Return the resultant sum return sum; } // Function to insert a new node // into the Binary Search Tree static Node insert(Node node, int data) { // Base Case if (node == null ) return newNode(data); // If the data is less than the // value of the current node if (data <= node.val) // Recur for left subtree node.left = insert(node.left, data); // Otherwise else // Recur for the right subtree node.right = insert(node.right, data); // Return the node return node; } // Driver Code public static void main(String[] args) { /* Let us create following BST 10 / \ 5 15 / \ \ 3 7 18 */ 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)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach from collections import deque # Class for node of the Tree class Node: def __init__( self ,v): self .val = v self .left = None self .right = None # Function to perform level order # traversal on the Tree and # calculate the required sum def rangeSumBST(root, low, high): sum = 0 # Base Case if (root = = None ): return 0 # Stores the nodes while # performing level order traversal q = deque() # Push the root node # into the queue q.append(root) # Iterate until queue is empty while ( len (q) > 0 ): # Stores the front # node of the queue curr = q.popleft() # q.pop() # If the value of the node # lies in the given range if (curr.val > = low and curr.val < = high): # Add it to sum sum + = curr.val # If the left child is # not NULL and exceeds low if (curr.left ! = None and curr.val > low): # Insert into queue q.append(curr.left) # If the right child is not # NULL and exceeds low if (curr.right ! = None and curr.val < high): # Insert into queue q.append(curr.right) # Return the resultant sum return sum # Function to insert a new node # into the Binary Search Tree def insert(node, data): # Base Case if (node = = None ): return Node(data) # If the data is less than the # value of the current node if (data < = node.val): # Recur for left subtree node.left = insert(node.left, data) # Otherwise else : # Recur for the right subtree node.right = insert(node.right, data) # Return the node return node # Driver Code if __name__ = = '__main__' : # /* Let us create following BST # 10 # / \ # 5 15 # / \ \ # 3 7 18 */ root = None root = insert(root, 10 ) root = insert(root, 5 ) root = insert(root, 15 ) root = insert(root, 3 ) root = insert(root, 7 ) root = insert(root, 18 ) L, R = 7 , 15 print (rangeSumBST(root, L, R)) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Class for node of the Tree class Node { public int val; public Node left, right; }; // Function to create a new BST node static Node newNode( int item) { Node temp = new Node(); temp.val = item; temp.left = temp.right = null ; // Return the newly created node return temp; } // Stores the sum of all nodes // lying in the range [L, R] static int sum = 0; // Function to perform level order // traversal on the Tree and // calculate the required sum static int rangeSumBST(Node root, int low, int high) { // Base Case if (root == null ) return 0; // Stores the nodes while // performing level order traversal Queue<Node> q = new Queue<Node>(); // Push the root node // into the queue q.Enqueue(root); // Iterate until queue is empty while (q.Count!=0) { // Stores the front // node of the queue Node curr = q.Peek(); q.Dequeue(); // If the value of the node // lies in the given range if (curr.val >= low && curr.val <= high) { // Add it to sum sum += curr.val; } // If the left child is // not null and exceeds low if (curr.left != null && curr.val > low) // Insert into queue q.Enqueue(curr.left); // If the right child is not // null and exceeds low if (curr.right != null && curr.val < high) // Insert into queue q.Enqueue(curr.right); } // Return the resultant sum return sum; } // Function to insert a new node // into the Binary Search Tree static Node insert(Node node, int data) { // Base Case if (node == null ) return newNode(data); // If the data is less than the // value of the current node if (data <= node.val) // Recur for left subtree node.left = insert(node.left, data); // Otherwise else // Recur for the right subtree node.right = insert(node.right, data); // Return the node return node; } // Driver Code public static void Main(String[] args) { /* Let us create following BST 10 / \ 5 15 / \ \ 3 7 18 */ 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; Console.Write(rangeSumBST(root, L, R)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for the above approach // Class for node of the Tree class Node { // Function to create a new BST node constructor(item) { this .val=item; this .left= this .right= null ; } } // Stores the sum of all nodes // lying in the range [L, R] let sum = 0; // Function to perform level order // traversal on the Tree and // calculate the required sum function rangeSumBST(root,low,high) { // Base Case if (root == null ) return 0; // Stores the nodes while // performing level order traversal let q = []; // Push the root node // into the queue q.push(root); // Iterate until queue is empty while (q.length!=0) { // Stores the front // node of the queue let curr = q.shift(); // If the value of the node // lies in the given range if (curr.val >= low && curr.val <= high) { // Add it to sum sum += curr.val; } // If the left child is // not null and exceeds low if (curr.left != null && curr.val > low) // Insert into queue q.push(curr.left); // If the right child is not // null and exceeds low if (curr.right != null && curr.val < high) // Insert into queue q.push(curr.right); } // Return the resultant sum return sum; } // Function to insert a new node // into the Binary Search Tree function insert(node,data) { // Base Case if (node == null ) return new Node(data); // If the data is less than the // value of the current node if (data <= node.val) // Recur for left subtree node.left = insert(node.left, data); // Otherwise else // Recur for the right subtree node.right = insert(node.right, data); // Return the node return node; } // Driver Code /* Let us create following BST 10 / \ 5 15 / \ \ 3 7 18 */ 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)); // This code is contributed by patel2127 </script> |
32
Time Complexity: O(N)
Auxiliary Space: O(N)
Another Approach :
In this approach, we can directly apply In-Order traversal on the Binary Search Tree and if that node value lies in between the range [L, R] then we can simply add it to the sum.
C++
// C++ program for the above approach // This Code is contributed by Omkar Subhash Ghongade #include <bits/stdc++.h> using namespace std; // Class for node of the Tree class Node { public : int val; Node *left, *right; }; // Function to create a new BST node Node* newNode( int item) { Node* temp = new Node(); temp->val = item; temp->left = temp->right = NULL; // Return the newly created node return temp; } // Stores the sum of all nodes // lying in the range [L, R] int sum = 0; // Function to perform level order // traversal on the Tree and // calculate the required sum void rangeSumBST(Node* root, int low, int high, int * sum) { if (root != NULL) { // Giving a call to the left subtree rangeSumBST(root->left, low, high, sum); // checking if the value at that node is in the // range or not. if (root->val >= low && root->val <= high) *sum += root->val; // Giving a call to the right subtree rangeSumBST(root->right, low, high, sum); } } // Function to insert a new node // into the Binary Search Tree Node* insert(Node* node, int data) { // Base Case if (node == NULL) return newNode(data); // If the data is less than the // value of the current node if (data <= node->val) // Recur for left subtree node->left = insert(node->left, data); // Otherwise else // Recur for the right subtree node->right = insert(node->right, data); // Return the node return node; } // Driver Code int main() { /* Let us create following BST 10 / \ 5 15 / \ \ 3 7 18 */ 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, sum = 0; rangeSumBST(root, L, R, &sum); cout << sum; return 0; } |
Java
// Java program for the above approach // class for node of the tree class Node { int val; Node left, right; Node( int item) { val = item; left = right = null ; } } // class to store the sum of all nodes // lying in the range [L,R] class Sum { int sum = 0 ; } // function to perform level order // traversal on the tree and // calculate the required sum class BinaryTree { Node root; Sum sum; // function to create a new BST node Node newNode( int item) { return new Node(item); } // function to insert a new node // into the binary search tree Node insert(Node node, int data) { // base case if (node == null ) { return newNode(data); } // if the data is less than the // value of the current node if (data <= node.val) { // recur for left subtree node.left = insert(node.left, data); } else { // recur for the right subtree node.right = insert(node.right, data); } // return the node return node; } // function to perform level order // traversal on the tree and // calculate the required sum void rangeSumBST(Node root, int low, int high) { if (root != null ) { // giving a call to the left subtree rangeSumBST(root.left, low, high); // checking if the value at that node is in the // range or not if (root.val >= low && root.val <= high) { sum.sum += root.val; } // giving a call to the right subtree rangeSumBST(root.right, low, high); } } // driver code public static void main(String[] args) { BinaryTree tree = new BinaryTree(); Sum sum = new Sum(); tree.sum = sum; // Let us create following BST // 10 // / \ // 5 15 // / \ \ // 3 7 18 tree.root = tree.insert(tree.root, 10 ); tree.insert(tree.root, 5 ); tree.insert(tree.root, 15 ); tree.insert(tree.root, 3 ); tree.insert(tree.root, 7 ); tree.insert(tree.root, 18 ); int L = 7 ; int R = 15 ; tree.rangeSumBST(tree.root, L, R); System.out.println(sum.sum); } } // This code is contributed by codebraxnzt |
Python3
# Python program for the above approach # class for node of the tree class Node: def __init__( self , item): self .val = item self .left = None self .right = None # function to create a new BST node def newNode(item): return Node(item) # stores the sum of all nodes # lying in the range [L,R] sum = 0 # function to perform level order # traversal on the tree and # calculate the required sum def rangeSumBST(root, low, high): if (root is not None ): # giving a call to the left subtree rangeSumBST(root.left, low, high) # checking if the value at that node is in the # range or not if (root.val > = low and root.val < = high): global sum sum + = root.val # giving a call to the right subtree rangeSumBST(root.right, low, high) # function to insert a new node # into the binary search tree def insert(node, data): # base case if (node is None ): return newNode(data) # if the data is less than the # value of the current node if (data < = node.val): # recur for left subtree node.left = insert(node.left, data) #otherwise else : # recur for the right subtree node.right = insert(node.right, data) # return the node return node # driver code # Let us create following BST # 10 # / \ # 5 15 # / \ \ # 3 7 18 root = None root = insert(root, 10 ) insert(root, 5 ) insert(root, 15 ) insert(root, 3 ) insert(root, 7 ) insert(root, 18 ) L = 7 R = 15 rangeSumBST(root, L, R) print ( sum ) # this code is contributed by yash agarwal(yashagarwal2852002) |
C#
using System; // class for node of the tree class Node { public int val; public Node left, right; public Node( int item) { val = item; left = right = null ; } } // class to store the sum of all nodes // lying in the range [L,R] class Sum { public int sum = 0; } // function to perform level order // traversal on the tree and // calculate the required sum class BinaryTree { public Node root; public Sum sum; // function to create a new BST node public Node newNode( int item) { return new Node(item); } // function to insert a new node // into the binary search tree public Node insert(Node node, int data) { // base case if (node == null ) { return newNode(data); } // if the data is less than the // value of the current node if (data <= node.val) { // recur for left subtree node.left = insert(node.left, data); } else { // recur for the right subtree node.right = insert(node.right, data); } // return the node return node; } // function to perform level order // traversal on the tree and // calculate the required sum public void rangeSumBST(Node root, int low, int high) { if (root != null ) { // giving a call to the left subtree rangeSumBST(root.left, low, high); // checking if the value at that node is in the // range or not if (root.val >= low && root.val <= high) { sum.sum += root.val; } // giving a call to the right subtree rangeSumBST(root.right, low, high); } } // driver code static void Main( string [] args) { BinaryTree tree = new BinaryTree(); Sum sum = new Sum(); tree.sum = sum; // Let us create following BST // 10 // / \ // 5 15 // / \ \ // 3 7 18 tree.root = tree.insert(tree.root, 10); tree.insert(tree.root, 5); tree.insert(tree.root, 15); tree.insert(tree.root, 3); tree.insert(tree.root, 7); tree.insert(tree.root, 18); int L = 7; int R = 15; tree.rangeSumBST(tree.root, L, R); Console.WriteLine(sum.sum); } } |
Javascript
// this code is contributed by KIRTI AGARWAL(KIRTIAGARWAL23121999) // JavaScript program for the above approach class Node{ constructor(item){ this .val = item; this .left = null ; this .right = null ; } } // returns a new node function newNode(data){ return new Node(data); } // Stores the sum of all nodes // lying in the range [L, R] let sum = 0; // Function to perform level order // traversal on the Tree and // calculate the required sum function rangeSumBST(root, low, high){ if (root != null ){ // giving a call to the left subtree rangeSumBST(root.left, low, high); // checking if the value at that node is in the // range or not if (root.val >= low && root.val <= high){ sum += root.val; } // giving a call to the right subtree rangeSumBST(root.right,low, high); } } // function to insert a new node // into the Binary Search Tree function insert(node, data){ // base case if (node == null ) return newNode(data); // if the data is less than the // value of the current node if (data <= node.val){ // recur for left subtree node.left = insert(node.left, data); } // otherwise else { // recur for the right subtree node.right = insert(node.right,data); } // return the node return node; } // driver code /* Let us create following BST 10 / \ 5 15 / \ \ 3 7 18 */ 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; rangeSumBST(root, L, R); console.log(sum); |
32
Time Complexity: O(n), n is number of nodes in the tree.
Auxiliary Space: O(n), where n is the number of nodes in the tree
Contact Us