Count BST Nodes that Lie in a given Range

Problem Statement

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 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 subtrees into two parts: The left and right subtrees.

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

Sample Example

Input

N=7, L=9, R=17

Output 

5

Explanation

In this case, L=9 and H=17, so the nodes in this range are 10, 12, 15, 17, and 14. 

Approach

The approach to finding the no of nodes in BST which lie in a particular range is simple. In this approach, we will first check if the current node is in the range or not; if it is, then we will call for both left and right, and we will add 1 to the result obtained from left and right calls, else we know that according to the BST property, the nodes present in the left of a node are smaller and nodes present in the right are greater. So by using this property, we will see If it is feasible to go in left or right.

Algorithm

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

1. First, we create the node structure containing the Data, Left pointer, and Right pointer and make a range.
2. Create a function insert() to take input for inserting a new node.
3. Then, we create another function, findCount(), for counting BST nodes within the given range. In this function, we will check if the root == NULL. If it is NULL, then we return ‘count.’
4. In this function, we will check if the current node is present in the range of [L, H]. If it is, we will call for both left and right and add 1 to the result obtained from left and right calls,
5. If the current node does not satisfy the range of [L, H], we will either go to the left or right subtree.
6. If the value current node is smaller than the value of L, then we will make a call to the right subtree, else we will make a call to the left subtree.

Dry Run

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 key value 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

Step-1

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 the ‘count’.

COUNT = 1

Step-2

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

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

COUNT = 2

Step-3

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.

Step-4

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. The right subtree of 50 is useless since it will only contain values larger than 50.

Step-5

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.

Implementation in C++

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

// Structure of the binary search tree node
struct Tree
{
    int Data;
    struct Tree *Left;
    struct Tree *Right;

    Tree(int val)
    {
        this->Data = val;
        this->Left = this->Right = NULL;
    }
};

// Function for counting BST Trees that lie in the given range
int findCountOfTree(Tree *root, int Low, int High)
{

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

    /*
        Checking if the current Tree is in the range. If it does, then
        include it in ‘COUNT’ and call recursive function for left and
        right subtrees
    */
    if (root->Data <= High && root->Data >= Low)
    {
        return 1 + findCountOfTree(root->Left, Low, High) +
               findCountOfTree(root->Right, Low, High);
    }

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

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

// Driver Code
int main()
{

    // Let us consider this binary search tree.
    Tree *root = new Tree(8);
    root->Left = new Tree(4);
    root->Right = new Tree(50);
    root->Left->Left = new Tree(2);
    root->Left->Left->Left = new Tree(1);
    root->Left->Left->Left->Left = new Tree(0);
    root->Right->Left = new Tree(40);
    root->Right->Right = new Tree(100);
    root->Right->Right->Right = new Tree(110);
    root->Right->Right->Left = new Tree(90);
    int Low = 4;
    int High = 45;
    cout << "The count of the Nodes that lie in the range [" << Low << ", " << High << "] is " << findCountOfTree(root, Low, High) << ".";
    return 0;
}

 

Output

The count of the Nodes that lie in the range [4, 45] is 3.

Implementation in Java

// For counting the number of BST node in a given range
import java.util.*;

// Structure of the binary search tree node
class Tree
{
    int Data;
    Tree Left;
    Tree Right;

    Tree(int val)
    {
        this.Data = val;
        this.Left = this.Right = null;
    }
}

// Function for counting BST Trees that lie in the given range
class Main
{
    static int findCountOfTree(Tree root, int Low, int High)
    {
        // Base case
        if (root == null)
        {
            return 0;
        }

        /*
            Checking if the current Tree is in the range. If it does, then
            include it in ‘COUNT’ and call a recursive function for left and
            right subtrees
        */
        if (root.Data <= High && root.Data >= Low)
        {
            return 1 + findCountOfTree(root.Left, Low, High) +
                   findCountOfTree(root.Right, Low, High);
        }

        else if (root.Data < Low)
        {
            return findCountOfTree(root.Right, Low, High);
        }

        else
        {
            return findCountOfTree(root.Left, Low, High);
        }
    }

    // Driver Code
    public static void main(String[] args)
    {
        // Let us consider this binary search tree.
        Tree root = new Tree(8);
        root.Left = new Tree(4);
        root.Right = new Tree(50);
        root.Left.Left = new Tree(2);
        root.Left.Left.Left = new Tree(1);
        root.Left.Left.Left.Left = new Tree(0);
        root.Right.Left = new Tree(40);
        root.Right.Right = new Tree(100);
        root.Right.Right.Right = new Tree(110);
        root.Right.Right.Left = new Tree(90);

        int Low = 4;
        int High = 45;

        System.out.println("The count of the Nodes that lie in the range [" + Low + ", " + High + "] is " + findCountOfTree(root, Low, High) + ".");
    }
}

 

Output

The count of the Nodes that lie in the range [4, 45] is 3.

Complexity Analysis

Time Complexity 

The best-case time complexity is log(N), where ‘N’ is the number of nodes. This can be stated as log₂(N) = H, where ‘H’ is the height of BST. It is equivalent to,N = 2^H.

The height of BST and the number of 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 traverse through the whole tree, which will equal the number of nodes in the tree.

Space Complexity

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. 

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.

Read More - Time Complexity of Sorting Algorithms

Frequently Asked Questions

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

What is a binary search tree?

A binary search tree is a particular type of binary tree that works only if every tree node 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.

What are the advantages of using binary search trees?

Searching elements can take high time complexity, but searching 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.

What is the difference between the root node and the leaf node?

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

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. If the node is null, we will return 0. Else, we will return 1+ recursive call on left side + recursive call on right side.

Conclusion

In this blog, we learned about counting BST nodes, the working of BST nodes, and the code for counting BST nodes in a given specific range and its algorithm implementation. Try some binary search tree problems here on Coding Ninjas Studio to understand the working algorithms of binary search trees.

I hope this blog has helped you enhance your knowledge regarding the above Data Structures and Algorithms problem, and if you want to learn more, check out our articles on Coding Ninjas Studio. Enroll in our courses, refer to the test series and problems available, and look at the interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!