Remove BST Keys Outside the Given Range

Introduction 🤓

To remove BST keys outside the given range is a widely asked question. It is generally asked to check the problem-solving skills and aptitude of candidates. 

This article will discuss the problem to remove BST keys outside the given range. We recommend you try this problem first before preceding this article. We will use the division and traversal-based approach to solve this problem. Now let’s get started! 

Problem Statement 🤔

The problem is to remove BST keys outside the given range. It is a binary search tree problem. Here we are given the BST of integer value and a range. We have to remove the nodes which did not lie in the given range. 

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

Sample Example 🧐

Example:

Input: Given BST and the range [13,23]

Output:

Explanation: 

In the given example, remove BST keys outside the given range. We are given a BST and a range, i.e., [13,23]. Here, the elements which are not in the range will be removed from the BST. And then the tree will be rearranged accordingly afterwards. The below process will be executed to remove BST keys outside the given range.

Divide and Traverse Approach ➗↘️

We use the divide and traverse method to remove BST keys outside the given range. In this approach, we will divide the nodes into two different categories. First, the nodes which are inside the given range. And then the nodes which are outside the range. Either they are greater than the largest limit of the range. Or smaller than the lowest limit of the range.

The nodes which lie in the second category are removed. And the nodes in the first category are rearranged accordingly. 

Algorithm 🧑‍💻🌝

1. Make a structure to store a BST node.
2. Now create a function to do the in-order traversal of the tree.
3. Now create a recursive function to insert a key into a BST. The function will have three cases:
   1. If the value of the root node is null, create a new node and return it.
   2. If the key value is less than the root node, go for the left subtree
   3. If the key is more than the root node, go for the right subtree
4. Now create a function to remove BST keys outside the given range. We have two cases in it:
   1. If the key value of the root is smaller than the minimum element of the range. Delete it.
   2. If the key value of the root is larger than the maximum element of the range. Delete it.
5. Now modify the new tree according to the deletion process.

Implementation 🧑‍💻✨

#include <bits/stdc++.h>
using namespace std;
 
// To store a BST node
struct Node
{
    int data;
    Node* left = nullptr, *right = nullptr;
 
    Node() {}
    Node(int data): data(data) {}
};
 
// A function to perform in order traversal on the tree
void inordertraversal(Node* rootnode)
{
    if (rootnode == nullptr) {
        return;
    }
 
    inordertraversal(rootnode->left);
    cout << rootnode->data << " ";
    inordertraversal(rootnode->right);
}
 
// Now a recursive function to insert the key in a BST
Node* insertkey(Node* rootnode, int key)
{
    // If the value of the root node is null, create a new node and return it
    if (rootnode == nullptr) {
        return new Node(key);
    }
 
    // If the key is less than the root node, go for the left subtree
    if (key < rootnode->data) {
        rootnode->left = insertkey(rootnode->left, key);
    }
    // If the key is more than the root node, go for the right subtree
    else {
        rootnode->right = insertkey(rootnode->right, key);
    }
 
    return rootnode;
}
 
// Now function to remove BST keys outside the given range
Node* remove(Node* rootnode, int low, int high)
{
    // base case
    if (rootnode == nullptr) {
        return rootnode;
    }
 
    // Now recursively remove the left and right subtree first
    rootnode->left = remove(rootnode->left, low, high);
    rootnode->right = remove(rootnode->right, low, high);
 
    Node* curr = rootnode;
 
    // If the key value of the root is smaller than the minimum element of the range. Delete it.
    if (rootnode->data < low)
    {
        rootnode = rootnode->right;
        delete curr;
    }
// If the key value of the root is larger than the maximum element of the range. Delete it.
    else if (rootnode->data > high)
    {
        rootnode = rootnode->left;
        delete curr;
    }
 
    return rootnode;
}
 
int main()
{
     int keys[] = { 20, 15, 25, 13, 17, 23, 30, 11, 14, 16, 19, 21, 24, 29, 34 };

 
    Node* rootnode = nullptr;
    for (int key: keys) {
        rootnode = insertkey(rootnode, key);
    }
 
    // the valid range is 13 to 23
    rootnode = remove(rootnode, 13, 23);
    inordertraversal(rootnode);
 
    return 0;
}

Output:

Time Complexity ⏳

The time complexity of the post-order traversal approach. For the problem, 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 is O(1). As the BST is provided, it will not take any extra space. 

Also check out - Inorder Predecessor