Home » Interview coding problems/challenges

Delete nodes greater than or equal to k in a BST

In this article, we are going to see how to delete nodes having value greater than or equal to K?
Submitted by Radib Kar, on February 13, 2019

Problem statement:

Given a BST and a value x, write a function to delete the nodes having values greater than or equal to x. The function will return the modified root.

Example:

Input BST
      8
    /  \
   4    10
  / \   / \
 3   5  9  11

Input X:  10

After deletion:


     8
    /  \
   4    9
  / \   
 3   5  

Solution:

Basic properties of BST:

1. All node values are distinct.
2. The left child node is always smaller than the root & right child node is always greater than the root.

Thus it's clear whenever a root has a value greater than or equal to the input value X, the entire right subtree and root need to be deleted, but not the left one.

Algorithm:

FUNCTION buildTree (root,X)
    IF (root==NULL)
        Return NULL;
    END IF
    IF (root->data is equal to X)
        return root->left; //returning the left subtree basically
    ELSE IF(root->data>key)
        //recur for the left subtree since left subtree may also have nodes 
        //that need to be deleted due to greater or equal values
        return buildTree(root->left, X); 
    ELSE
        //root is not at all to be deleted, same for left subtree, 
        //recursively process right subtree
        root->right=buildTree(root->right, X);
        return root;
END FUNCTION

The above function actually builds the tree deleting the nodes having greater and equal value than X.

Example with Explanation:

Nodes are represented by respected values for better understanding
      8
    /  \
   4    10
  / \   / \
 3   5  9  11

Input X:  10

At main we callbuildTree (8, 10)
------------------------------------------------

buildTree (8, 10)
root not NULL
8<10
Thus root->left= 8->left
root->right=buildTree (8->right, 10) //buildTree (10, 10)
------------------------------------------------

buildTree (10, 10)
root not NULL
10==10
Thus return root->left= 10->left=9
------------------------------------------------

Hence At buildTree (8, 10)
Thus root->left= 8->left
root->right=9 (9 is the root to the remaining subtree which is NULL here luckily)

So the tree actually becomes
     8
   / \
  4     9
 / \ 
3   5 

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

class Node{
	public:             
	int data;           //value
	Node *left;    //pointer to left child
	Node *right;   //pointer to right child
};

// creating new node
Node* newnode(int data)  
{ 
	Node* node = (Node*)malloc(sizeof(Node)); 
	node->data = data; 
	node->left = NULL; 
	node->right = NULL; 
	return(node); 
}

Node* buildTree(Node* root,int key){
	if(!root)
		return NULL;
	if(root->data==key){
		return root->left; //only left subtree not deleted
	}
	else if(root->data>key)
		return buildTree(root->left,key); //recur for left subtree
	else{
		//root not deleted
		//left subtree not deleted
		//buld right subtree
		root->right=buildTree(root->right,key); 
		return root;
	}
}

Node* deleteNode(Node* root, int key)
{
	root=buildTree(root,key);
	return root; 
}

void levelwisedisplay(Node *root)
{
	//to display the tree level wise
	queue<Node*> q;

	Node* temp;
	int count=0;
	q.push(root);
	q.push(NULL);

	while(!q.empty()){
		temp=q.front();
		q.pop();

		if(temp==NULL){
			if(!q.empty())
				q.push(NULL);
			cout<<"\nend of level "<<count++<<endl;
		}
		else{
			cout<<temp->data<<" ";
			if(temp->left)
				q.push(temp->left);
			if(temp->right)
				q.push(temp->right);
		}
	}
	return ;
}

int main(){
	cout<<"tree is built as per example\n";

	Node *root=newnode(8); 
	root->left= newnode(4); 
	root->right= newnode(10); 
	root->right->right=newnode(11);
	root->right->left=newnode(9);
	root->left->left=newnode(3); 
	root->left->right=newnode(5);

	printf("Displaying level wise\n");
	levelwisedisplay(root);

	root=deleteNode(root,10);//as per example

	printf("after deleting nodes greater or equal to 10\n");
	levelwisedisplay(root);

	return 0;
}

Output

tree is built as per example
Displaying level wise
8      
end of level 0
4 10   
end of level 1
3 5 9 11      
end of level 2
after deleting nodes greater or equal to 10
8      
end of level 0
4 9    
end of level 1
3 5    
end of level 2