Q:

# Delete nodes greater than or equal to k in a BST

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

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