# 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
```

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates