Remove BST nodes having a value in the given range.

Vaibhav Agarwal
Last Updated: May 13, 2022

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.  

Prerequisites

To delete the nodes in the binary search tree. To know about this, you can refer to this link

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.

Frequently asked questions

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

Thank you for reading. 

Until then, Keep Learning and Keep Coding.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think