# 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.

## 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,

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’.

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

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

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.

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.

2. Then 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.

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

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).

Output-

## 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.

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:

## 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!