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
Basic properties of BST:
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:
The above function actually builds the tree deleting the nodes having greater and equal value than X.
Example with Explanation:
C++ Implementation:
Output