Count BST nodes that lie in a given range
Given the head of a Binary Search Tree (BST) and a range (l, h), count the number of nodes that lie in the given range (l, h).
Examples:
Input: Range: [5, 45]
10
/ \
5 50
/ / \
1 40 100
Output: 3
Explanation: There are three nodes in range, 5, 10 and 40Input: Range: [10, 100]
10
/ \
5 50
/ / \
1 40 100
Output: 4
Approach:
Traverse the given binary search tree starting from root. For every node check if this node lies in range, if yes, then add 1 to result and recur for both of its children. If current node is smaller than low value of range, then recur for right child, else recur for left child.
Follow the below steps to Implement the idea:
- Traverse the tree starting from the root.
- If root->data is equal to high and root->data is equal to low return 1.
- If root->data <= high and root->data >= low then return 1 + count on left of root + count on right of root.
- Else if root->data < low return count on right of root.
- Else if root->data > high return count on left of root.
Below is the implementation of the above approach.
C++
// C++ program to count BST nodes within a given range #include<bits/stdc++.h> using namespace std; // A BST node struct node { int data; struct node* left, *right; }; // Utility function to create new node node *newNode( int data) { node *temp = new node; temp->data = data; temp->left = temp->right = NULL; return (temp); } // Returns count of nodes in BST in range [low, high] int getCount(node *root, int low, int high) { // Base case if (!root) return 0; // Special Optional case for improving efficiency if (root->data == high && root->data == low) return 1; // If current node is in range, then include it in count and // recur for left and right children of it if (root->data <= high && root->data >= low) return 1 + getCount(root->left, low, high) + getCount(root->right, low, high); // If current node is smaller than low, then recur for right // child else if (root->data < low) return getCount(root->right, low, high); // Else recur for left child else return getCount(root->left, low, high); } // Driver program int main() { // Let us construct the BST shown in the above figure node *root = newNode(10); root->left = newNode(5); root->right = newNode(50); root->left->left = newNode(1); root->right->left = newNode(40); root->right->right = newNode(100); /* Let us constructed BST shown in above example 10 / \ 5 50 / / \ 1 40 100 */ int l = 5; int h = 45; cout << "Count of nodes between [" << l << ", " << h << "] is " << getCount(root, l, h); return 0; } |
Java
// Java code to count BST nodes that // lie in a given range class BinarySearchTree { /* Class containing left and right child of current node and key value*/ static class Node { int data; Node left, right; public Node( int item) { data = item; left = right = null ; } } // Root of BST Node root; // Constructor BinarySearchTree() { root = null ; } // Returns count of nodes in BST in // range [low, high] int getCount(Node node, int low, int high) { // Base Case if (node == null ) return 0 ; // If current node is in range, then // include it in count and recur for // left and right children of it if (node.data >= low && node.data <= high) return 1 + this .getCount(node.left, low, high)+ this .getCount(node.right, low, high); // If current node is smaller than low, // then recur for right child else if (node.data < low) return this .getCount(node.right, low, high); // Else recur for left child else return this .getCount(node.left, low, high); } // Driver function public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); tree.root = new Node( 10 ); tree.root.left = new Node( 5 ); tree.root.right = new Node( 50 ); tree.root.left.left = new Node( 1 ); tree.root.right.left = new Node( 40 ); tree.root.right.right = new Node( 100 ); /* Let us constructed BST shown in above example 10 / \ 5 50 / / \ 1 40 100 */ int l= 5 ; int h= 45 ; System.out.println( "Count of nodes between [" + l + ", " + h+ "] is " + tree.getCount(tree.root, l, h)); } } // This code is contributed by Kamal Rawal |
Python3
# Python3 program to count BST nodes # within a given range # Utility function to create new node class newNode: # Constructor to create a new node def __init__( self , data): self .data = data self .left = None self .right = None # Returns count of nodes in BST in # range [low, high] def getCount(root, low, high): # Base case if root = = None : return 0 # Special Optional case for improving # efficiency if root.data = = high and root.data = = low: return 1 # If current node is in range, then # include it in count and recur for # left and right children of it if root.data < = high and root.data > = low: return ( 1 + getCount(root.left, low, high) + getCount(root.right, low, high)) # If current node is smaller than low, # then recur for right child elif root.data < low: return getCount(root.right, low, high) # Else recur for left child else : return getCount(root.left, low, high) # Driver Code if __name__ = = '__main__' : # Let us construct the BST shown in # the above figure root = newNode( 10 ) root.left = newNode( 5 ) root.right = newNode( 50 ) root.left.left = newNode( 1 ) root.right.left = newNode( 40 ) root.right.right = newNode( 100 ) # Let us constructed BST shown in above example # 10 # / \ # 5 50 # / / \ # 1 40 100 l = 5 h = 45 print ( "Count of nodes between [" , l, ", " , h, "] is " , getCount(root, l, h)) # This code is contributed by PranchalK |
C#
using System; // C# code to count BST nodes that // lie in a given range public class BinarySearchTree { /* Class containing left and right child of current node and key value*/ public class Node { public int data; public Node left, right; public Node( int item) { data = item; left = right = null ; } } // Root of BST public Node root; // Constructor public BinarySearchTree() { root = null ; } // Returns count of nodes in BST in // range [low, high] public virtual int getCount(Node node, int low, int high) { // Base Case if (node == null ) { return 0; } // If current node is in range, then // include it in count and recur for // left and right children of it if (node.data >= low && node.data <= high) { return 1 + this .getCount(node.left, low, high) + this .getCount(node.right, low, high); } // If current node is smaller than low, // then recur for right child else if (node.data < low) { return this .getCount(node.right, low, high); } // Else recur for left child else { return this .getCount(node.left, low, high); } } // Driver function public static void Main( string [] args) { BinarySearchTree tree = new BinarySearchTree(); tree.root = new Node(10); tree.root.left = new Node(5); tree.root.right = new Node(50); tree.root.left.left = new Node(1); tree.root.right.left = new Node(40); tree.root.right.right = new Node(100); /* Let us constructed BST shown in above example 10 / \ 5 50 / / \ 1 40 100 */ int l = 5; int h = 45; Console.WriteLine( "Count of nodes between [" + l + ", " + h + "] is " + tree.getCount(tree.root, l, h)); } } // This code is contributed by Shrikant13 |
Javascript
<script> // javascript code to count BST nodes that // lie in a given range /* * Class containing left and right child of current node and key value */ class Node { constructor(item) { this .data = item; this .left = this .right = null ; } } // Root of BST var root = null ; // Returns count of nodes in BST in // range [low, high] function getCount( node , low , high) { // Base Case if (node == null ) return 0; // If current node is in range, then // include it in count and recur for // left and right children of it if (node.data >= low && node.data <= high) return 1 + this .getCount(node.left, low, high) + this .getCount(node.right, low, high); // If current node is smaller than low, // then recur for right child else if (node.data < low) return this .getCount(node.right, low, high); // Else recur for left child else return this .getCount(node.left, low, high); } // Driver function root = new Node(10); root.left = new Node(5); root.right = new Node(50); root.left.left = new Node(1); root.right.left = new Node(40); root.right.right = new Node(100); /* * Let us constructed BST shown in above example 10 / \ 5 50 / / \ 1 40 100 */ var l = 5; var h = 45; document.write( "Count of nodes between [" + l + ", " + h + "] is " + getCount(root, l, h)); // This code contributed by aashish1995 </script> |
Count of nodes between [5, 45] is 3
Time complexity: O(H + k) where h is the height of BST and k is the number of nodes in the given range.
Auxiliary Space: O(n)