Count BST Subtrees that Lie in a Given Range

Introduction 🤓

Operation on BST subtrees is a widely asked question in interviews. It is generally asked to check the problem-solving skills and aptitude of candidates. 

This article will discuss the problem to count BST subtrees that lie in a given range. We will use post order traversal approach to solve this problem. Now let’s get started! 

Problem Statement 🤔

The problem is to count BST subtrees that lie in a given range. It is a binary search tree problem. Here we are given the BST of integer value and a range. We have to return the count of the nodes and nodes under other nodes, i.e. subtrees. Which lie in that given range. 

Let’s understand this problem statement with the help of an example.   

Sample Examples 🧐

Example 1: Given Range [10,25]

Input:

Output:

Explanation:

We have to count BST subtrees that lie in a given range of [10,25]. Here, we find 6 such sub-trees. The subtrees' method is finding the nodes' value in between the given range. And if those nodes have children and their values are in range. Then we count them as sub-trees. 

Example 2: Given range [18,26]

Output:

Explanation:

We have to count BST subtrees that lie in a given range of [18,26]. Here, we find 4 such sub-trees. The subtrees' method is finding the nodes' value in between the given range. And if those nodes have children and their values are in range. Then we count them as sub-trees.

Post-Order Traversal Approach💻

To solve the problem, count BST subtrees that lie in a given range. We are using a post-order traversal approach. In this approach, we will implement post-order traversal on a given BST. Then for any node, if both of its left and right subtrees are within the range. Along with the node itself. We can say that the subtree associated with this node is also within the range.

Let’s discuss the algorithm of this approach.

Algorithm 

1. Make a structure to store a BST node.
    
2. Now create a recursive function to insert a key into a BST. The function will have three cases:
   • If the root value is null. Then create a new node and return it.
   • If the given key is less than the root node value. Then recur for the left subtree.
   • Otherwise, now recur to the right subtree.
      
3. Now create a function to count subtrees in a BST whose nodes lie within a given range.
    
4. Return true if the whole subtree rooted at the given node is within range.
    
5. Initialise the count variable for subtree count.
    
6. Increase the subtree count by one and return true if the root node, both left and right subtrees, are within the range.

Implementation 

#include <bits/stdc++.h>
using namespace std;
 
// To store a BST node
struct Node
{
    int data;
    Node *left, *right;
 
    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};
 
// The recursive function to insert a key into a BST
Node* insertkey(Node* rootnode, int key)
{
    // when the root is null. Create a new node and return it.
    if (rootnode == nullptr) 
    {
        return new Node(key);
    }
 
    // when the given key is less than the root node, recur for the left subtree
    if (key < rootnode->data) 
    {
        rootnode->left = insertkey(rootnode->left, key);
    }
 
    // otherwise, go for the right subtree
    else 
    {
        rootnode->right = insertkey(rootnode->right, key);
    }
 
    // now return root node
    return rootnode;
}
 
// A function to count BST subtrees that lie in a given range. It will return true if the whole subtree rooted at the given node is within range
bool SubTrees(Node* root, int low, int high, int &count)
{
    // base case
    if (root == nullptr) 
    {
        return true;
    }
 
    bool left = SubTrees(root->left, low, high, count);
    bool right = SubTrees(root->right, low, high, count);
 
    // now increasing the subtree count by 1 and return true if the root node, both left and right subtrees are within the given range. 
    if (left && right && (root->data >= low && root->data <= high))
    {
        count++;
        return true;
    }
 
    return false;
}
 
int main()
{
    // the range of input
    int l = 10, h = 25;
 
    // BST keys to construct BST 
    int keys[] = { 20, 30, 25, 27, 35, 23, 15, 13, 14, 17, 11 };
 
    // construct BST
    Node* root = nullptr;
    for (int key: keys) {
        root = insertkey(root, key);
    }
 
    // counting the number of subtrees
    int count = 0;
    SubTrees(root, l, h, count);
   cout << "The count of subtrees in [" << l << ", " << h << "] is " << count;
 
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Time Complexity ⏳

The time complexity of the post-order traversal approach. For the problem, count BST subtrees that lie in a given range, is O(n), i.e., linear. Here n is the size of BST. It is because we are traversing the tree in a bottom-up manner. And we are transferring information from children to the parent node.

Space Complexity 🌌

The space complexity of the approach, for the problem, count BST subtrees that lie in a given range, is O(h). It is because this approach will need space proportional to the height of the tree.