1.
Introduction
1.1.
Binary Search Tree
1.2.
Prerequisites
1.3.
Sample Examples
2.
Solution Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
4.
Key takeaways
Last Updated: Mar 27, 2024

Remove BST nodes having a value in the given range.

Introduction

The problem states that we need to remove BST nodes having a value in the given range. After removing all the nodes in the range [min-max], the final output should also be the binary search tree.  Let’s recap what is Binary search tree in brief, and what are the prerequisites to solve this question.

Binary Search Tree

A binary Search Tree is a particular type of binary tree in which keys in the left subtree are always smaller than the root node, and nodes in the right subtree are always greater than the root node. To know more about the Binary search tree, you can refer to this.

Sample Examples

Input: Given the BST as shown below, and range is [4,7].

Output:

ExplanationThe node values in the range [4,7] are 4,5,6 and 7 in the given binary search tree. Hence we have remove BST nodes having a value in the given range.

Input: Given the BST as shown below, and range is [90,100].

Output:

ExplanationThe node values in the range [90,100] are 91 and 99 only in the given binary search tree. Hence we have remove BST nodes having a value in the given range.

Solution Approach

To remove BST nodes having a value in the given range[min, max], we can have two possible cases:

1. Nodes are in the given range
2. Nodes are not in the given range.

If nodes are not in the given range, we need not do anything. We will just move to the next node, but when nodes are in the given range, we need to delete the nodes in the binary search tree.  The idea to solve this problem is simple; we will traverse the tree in preorder traversal, i.e., we will make sure that for any current node, its left and right subtrees are already processed. Now, whenever we find the node in the given range, we will simply call the delete function of BST.

Algorithm

1. Traverse the tree in the preorder traversal by fixing the left and right subtrees of the node.
2. Now check for the current node value is in the given range or not.
3. If the value is not in the given range, do nothing.
4. If the current node is in the given range, call for delete node function.
5. Check for base condition. If the root value is NULL, return NULL.

Implementation in C++

``````// C++ implementation of the above approach
#include <bits/stdc++.h>

using namespace std;

// structure of the binary search tree node
class Node {
public:
int value;
Node * left, * right;
Node(int value) {
this -> value = value;
left = NULL;
right = NULL;
}
};
Node * leftMost(Node * root) {
if (!root)
return NULL;
while (root -> left)
root = root -> left;
return root;
}
// A Utility function to delete the nodes in the Binary search tree
Node * deleteNode(Node * root) {
// If nodes have only the single child or no child
if (!root -> left) {
Node * child = root -> right;
root = NULL;
return child;
} else if (!root -> right) {
Node * child = root -> left;
root = NULL;
return child;
}
Node * next = leftMost(root -> right);

// copying the content of inorder successor to this node
root -> value = next -> value;

// deleting the inorder successor
root -> right = deleteNode(root -> right);

return root;
}

// A utility function to remove BST nodes having a value in the given range
Node * BSTremoveRange(Node * root, int min, int max) {

// Base case
if (!root)
return NULL;

// traversing in the preorder fashion by fixing the left and right subtrees
root -> left = BSTremoveRange(root -> left, min, max);
root -> right = BSTremoveRange(root -> right, min, max);

// if given root value is in Range then call deleteNode function
if (root -> value >= min && root -> value <= max)
// delete the nodes in the binary search tree
return deleteNode(root);

// if root value is not in range
return root;
}

// A utility function to insert a new
// Node with given value in BST
Node * insert(Node * root, int value) {
Node * newnode = new Node(value);

// Pointer to start iterating the array
// from the root node
Node * curr = root;

// prev pointer will note the trailing of start pointer
Node * prev = NULL;

while (curr != NULL) {
prev = curr;
if (value < curr -> value)
curr = curr -> left;
else
curr = curr -> right;
}

// If the prev is NULL it means that the tree is empty
// The new node is the root node
if (prev == NULL)
prev = newnode;

// if the new value is lesser than the leaf node
// make the newNode as the left child of leaf node
else if (value < prev -> value)
prev -> left = newnode;

// otherwise make the newNode as right child of leaf node
else
prev -> right = newnode;

// Returns the prev pointer
// where we have inserted the newNode
return prev;
}

void Inorder(Node * root) {
// if the root node is NULL
if (!root)
return;
Inorder(root -> left);
// printing the root value
cout << root -> value << " ";
Inorder(root -> right);
return;
}

// Driver Program to test above functions
int main() {
Node * root = NULL;
root = insert(root, 41);
int nodesValues[] = { 20, 65, 11, 29, 50, 91, 32, 72, 99 };
for (int i = 0; i < 9; i++) {
insert(root, nodesValues[i]);
}

cout << "Inorder Traversal before Deletion : ";
Inorder(root);

root = BSTremoveRange(root, 20, 40);

cout << endl << "Inorder Traversal before Deletion: ";
Inorder(root);

cout << endl;
return 0;
}``````

Output:

``````Inorder Traversal before Deletion : 11 20 29 32 41 50 65 72 91 99
Inorder Traversal before Deletion: 11 41 50 65 72 91 99``````

Complexity Analysis

Time Complexity: O(n*h)

Explanation: O(n*h)  because in the worst case, every node can be in the range of [min - max], so for every node, you have to go and find its successor in O(h).

Space ComplexityO(1)

Explanation: We are just constants; it will not be considered extra Space. Hence space complexity is O(1)  to remove BST nodes having a value in the given range.

Q1. What is the difference between a binary tree and a binary search tree?

Ans. A tree that has a maximum of 2 children is called a binary tree, whereas a binary search tree is a particular binary tree having the following properties. Keys in the left subtree are always smaller than the root’s node, whereas keys in the right subtree are greater than the root’s node.

Q2. What is inorder traversal ?

Ans. In inorder traversal, we first traverse the left subtree, then visit the root and then traverse the right subtree.

Q3. How to get the sorted output from the binary search tree?

Ans. Traversing the binary search tree in the inorder traversal gives us the sorted output.

Key takeaways

This article discussed how to Remove BST nodes having a value in the given range. We hope you understand the problem and solution properly. Now you can try the more similar questions on BST.

If you are a beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free
Check out this problem - Largest BST In Binary Tree