Count BST Nodes that lie in a given Range

Sneha Mallik
Last Updated: May 13, 2022

Introduction

 

Consider a binary search tree(BST) with range [L, H] where ‘L’ denotes the lowest element, and ‘H’ denotes the highest element. Our task is to count the nodes in the binary search tree that lie in this given range.

 

Points for consideration are:

  1. The elements with values lesser than the root element go to the left side.
  2. The elements with values greater than the root element go to the right side.


A binary search tree divides all of its subtrees into two parts: Left subtree and Right subtree.

Left Subtree(Keys) < Node(Key) < Right Subtree(Keys)

 

Read more about binary search trees.

 

Working of counting BST nodes

 

Let us consider an example.

 

 

 

Here, L = 4 and H = 45 are given to us. Therefore, 4 <= N <=45 is the range for N, where ‘N’ is the number of nodes. We will take a variable ‘COUNT’, which will count the number of nodes in the range inclusive of ‘L’ and ‘H’.

 

Initializing the ‘count’ of nodes in the given range with 0,

COUNT = 0

 

First, we’ll go to the root node- 

 

 

We will check if it is present in the range given. Since 4 <= 8 <= 45, we will increment ‘count’.

COUNT = 1

 

Then we move to the left subtree, and now the current node will be 4. 

 

 

 

Since 4 <= 4 <= 45, we will increase ‘count’.

COUNT = 2

 

Then we’ll move to the left of 4, and the current node is now 2 since 2 < 4, ‘count’ remains the same as we know that the left subtree elements are lesser than the root node. Hence, the remaining left element must be less than 2, which doesn’t come under the given range. Therefore we’ll move on to the right subtree of 4. Here we check if 4 has any right child element. Since 4 does not have any right child element, it returns to its root node, i.e., 8.

 

Now we’ll go to the right subtree of 8, a node with a value of 50.

 

 

50 > 45, which means its left subtree contains elements less than 50 which might lie in our given range.

 

We then check the left subtree of 50 with node value 40.

 

 

Here, 40 < 45 will come into the given range, incrementing the ‘count’ variable.

COUNT = 3

 

The node having value 40 does not have any child elements. Hence it will return to its root element, i.e., 50 with count value = 3. The program ends here as 50 is more than 45 and, therefore, lies outside the range.

 

The node values between range [4, 45] are 8, 4 and 40, so there are 3 nodes in the binary search tree.

 

Algorithm for counting BST nodes

 

The idea behind the code is to traverse through the array following the below points.

 

  1. First, we create the node structure, which contains the DataLeft pointer and Right pointer, and we make a range.
Struct Node{
    int data;
    Node *left;
    Node *right;

    Node(int x){
    data = x;
    left= NULL;
    right=NULL;
    }
};

 

 

2. Then create a function insert() to take input for inserting a new node.

Node *insert(Node *root, int data){
    if(root == NULL)
        root = new Node(data);
    else if(data < root->data)
        root->left = insert(root->left, data);
    else
        root->right = insert(root->right, data);
}


3. Then we create another function, findCount() for counting BST nodes within the given range.

 

4. We will check if the root == NULL. If it is NULL, then we return ‘count’.

/*

    Function to find the counting of BST nodes that lie in the 

    given range

*/

int findCount(Node *root, int L, int H){
    int count = 0;
    if(root == NULL){
        return count;
    }
    if(root->data >=L && root->data <= H ){
        count++;
    }
    return count + findCount(root->left, L, H) + 
    findCount(root->right, L, H);
}


5. If root is not null then we will check if the root -> Data <= H && root -> Data >= L, then we will return (count+1) back.


6. Then we will return count + findCount (root -> left, L, H) + findCount (root -> right, L, H).

Node

/    \

/       \

                                                    Node does       Node

                                                     not exist              exists

                                                       /                           /    

                                                      /                           /      

                                                    0                    Check 

                                                                    current node

                                                                          /     \

                                                                         /       \

                                                          If possible       If possible

                                                            on left             on right

                                                                /                        \

                                                               /                          \

                                                      Go to left                 Go to right

 

Code in C++

//For counting the number of BST nodes in a given range
#include <bits/stdc++.h>
using namespace std;

//Structure of the binary search tree node
struct node{
    int Data;
    struct nodeLeft;
    struct nodeRight;
};

//Function to create a new node
node* newNode (int Data){
    node* temp = new node;
    temp -> Data = Data;
    temp -> Left = temp -> Right = NULL;
    return temp;
}

//Function for counting BST nodes that lie in the given range
int findCountOfNode(node* root, int Low, int High){

    //Base case
    if(!root){
        return 0;
    }

    if(root -> Data == High && root -> Data == Low){
        return 1;
    }

    /*

        Checking if the current node is in the range. If it does, then 

        include it in ‘COUNT’ and call recursive function for left and 

        right children of it

    */
    if(root -> Data <= High && root -> Data >= Low){
        return 1 + findCountOfNode(root -> Left, Low, High) + 
        findCountOfNode(root -> Right, Low, High);  
    }


    else if(root -> Data < Low){
        return findCountOfNode(root -> Right, Low, High);
    }


    else{
        return findCountOfNode(root -> Left, Low, High);
    }
}

//Driver Code
int main(){


    //Let us consider this binary search tree.
    node *root = newNode(32);
    root -> Left = newNode(22);
    root -> Right = newNode(12);
    root -> Left -> Left = newNode(10);
    root -> Left -> Right = newNode(45);
    root -> Right -> Left = newNode(50);
    root -> Right -> Right = newNode(65);
    int Low = 10;
    int High = 40;
    cout << "The count of the nodes that lie in the range [" << Low << 
    ", " << High << "] is " << findCountOfNode(root, Low, High) << "."
    return 0;
}

 

Output-

The count of nodes that lie in the range [1040] is 4.

 

Time Complexity Analysis

 

The best-case time complexity is log(N), where ‘N’ is the number of nodes.

This can be stated as,

                                                                log2(N) = H, where ‘H’ is the height of BST

It is equivalent to,

N = 2H

 

The height of BST and the number of the nodes are related exponentially; we take a log to find the tree’s height backward. All the BST operations(insert, search or delete operation) have O(H) time complexity.

 

We will take the number of elements between ‘Low’ and ‘High’ as K, with O(K) time complexity. 

 

Thus, adding both the time complexities, 

O(log N) + O(K) => O(H) + O(K)

                                                                          => O(H + K)

 

O(H + K) or [O(log n) + O(K)] is the time complexity for counting BST nodes, where ‘H’ is the height of the binary search tree, and ‘K’ is the number of nodes that lie in the given range.

 

The worst time complexity for counting BST nodes is O(N), where ‘N’ is the total number of elements in the binary search tree as we will traverse through the whole tree that will be equal to the number of nodes in the tree.

 

Space Complexity Analysis

 

O(N) space complexity will be used for counting BST nodes where ‘N’ is the total number of nodes in the tree. Space complexity for the tree is proportional to the number of nodes of the binary search tree. Space complexity is the maximum amount of stack memory allocated to search the entire BST recursively.

 

In an average or best-case scenario, the height of the BST would be about log(N). Hence, space complexity will be O(log N).

 

In the worst-case scenario,  the space complexity will be O(N), where the tree is a sorted linked list branching right with increasing values with 1.

 

Frequently Asked Questions

1. What is a binary tree?
A binary tree is a tree that can have a maximum of two child nodes. The following properties are of a binary tree:-

  • A node(root) that stores the data of an element
  • A left subtree, and
  • A right subtree
     

2. What is a binary search tree?
A binary search tree is a particular type of binary tree that works only if every node of the tree satisfies the following conditions:-

  • The element at the root node must be greater than every element in the left subtree.
  • The element at the root node must be smaller than every element in the right subtree.
     

3. What are the advantages of using binary search trees?
Searching elements can take high time complexity, but search in binary search trees is much more efficient since it uses a recursive way to shorten each subtree in a single recursive call. It uses O( log N ) time complexity and can take up to O(N) in the worst-case situation when the tree will be of skewed type. It is way faster than arrays and linked lists for insertion and deletion operations.

 

4. What is the difference between the root node and leaf node?
The top node or the first node in a tree is called the root node, whereas the leaf nodes are the last nodes, or we can say, leaf nodes are those nodes that don’t contain any children.


5. How are BST nodes counted?
We will have a node, and there can be two possibilities, either the node is null, and the second possibility is that the node is not null.

Pseudocode:

if(node == NULL){

    return 0;

}
if(node != NULL){
    return (+ recursive(node -> left) + recursive(node -> 

    right));

}

 

Key Takeaways

 

In this blog, we learned about counting BST nodes, the working of BST nodes, and the code on counting BST nodes in a given specific range and its algorithm implementation.

 

Try some binary search tree problems here on CodeStudio to understand the working algorithms of binary search trees. To be more confident in data structures and algorithms, try out our DS and Algo Course.

 

Happy learning!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think