1.
Introduction 🤓
1.1.
Problem Statement 🤔
1.2.
Sample Example 🧐
2.
Divide and Traverse Approach ➗↘️
2.1.
Algorithm 🧑‍💻🌝
2.2.
Implementation 🧑‍💻✨
2.2.1.
Time Complexity ⏳
2.2.2.
Space Complexity 🌌
3.
3.1.
How do you recursively remove a BST?
3.2.
What is the deletion time complexity in a BST?
3.3.
What are the similar problems like remove BST keys outside the given range?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

# 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

### How do you recursively remove a BST?

To recursively remove a BST, you can follow:

1. If there are no children, delete.
2. If there is only one child, copy that child to the node.
3. If there are two children - Determine the next highest element in the right subtree (in-order successor). Replace the to-be-removed node with its inorder successor. Remove the duplicate inorder successor.

### What is the deletion time complexity in a BST?

Time complexity is generally O(h).

To delete element:

1. We must traverse all elements until we find 1. (in order 3, 2, 1).
2. As a result, deletion in a binary tree has a worst-case complexity of O(n). Time complexity is generally O(h).

### What are the similar problems like remove BST keys outside the given range?

Some problems that are similar to removing BST keys outside the given range are Count BST subtrees that lie in a given range, Print BST keys in the given valid range.

## Conclusion

This article briefly discussed the problem to remove BST keys outside the given range. We used an in-order traversal-based approach to find the solution to the given problem.

We hope that this blog has helped you enhance your knowledge about the problem to remove BST keys outside the given range. And if you would like to learn more, check out our articles Largest BST subtree in the given binary treeRange Sum of BSTLowest common ancestor in a BST, and  Count BST nodes that lie in a given range. You can also refer to our guided path on the basics of java and many more on our Website.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundles for placement preparations.

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

Happy learning!

Live masterclass