C++ Program to prevent deletion of node having degree 0 or 1 in Binary Search Tree
Description:
using namespace std;
struct BST_node
{
int data;
struct BST_node *left, *right;
};
typedef struct BST_node node;
void in_order(node *root)
{
if (root)
{
in_order(root->left);
cout << root->data << " ";
in_order(root->right);
}
}
node *create_node(int d)
{
//create a new node
node *ptr = (node *)malloc(sizeof(node));
ptr->data = d;
ptr->right = ptr->left = NULL;
return ptr;
}
node *insert_node(node *root, int key)
{
//base case
if (!root)
return create_node(key);
//else recurse down the tree
if (key < root->data)
root->left = insert_node(root->left, key);
else
root->right = insert_node(root->right, key);
//if key is already present (root->data == key) then simply return the unchanged root
return root;
}
node *min_value(node *root)
{
node *current = root;
while (current && current->left != NULL)
current = current->left;
return current;
}
//this function delete the key and returns a new root
node *delete_node(node *root, int key)
{
//base condition
if (!root)
return root;
//------------------- locate the deletion --------------------------
//if key is less than it lies to lest sub tree else right sub tree
if (key < root->data)
root->left = delete_node(root->left, key);
else if (key > root->data)
root->right = delete_node(root->right, key);
else
{ //else the key is same as of root's key then this is the node is to be deleted
//case 1) if this node has 0 or 1 child
if (root->left == NULL)
{
cout << "\n"
<< root->data << " not having degree 2 can't delete :(" << endl;
return root;
}
else if (root->right == NULL)
{
cout << "\n"
<< root->data << " not having degree 2 can't delete :(" << endl;
return root;
}
//case 2) we reached here means root have 2 children so get the smallest from the right subtree
// (Means get the in-order successor)
node *temp = min_value(root->right);
//copy the in-order successor to this node
root->data = temp->data;
//now delete the in-order successor (temp)
root->right = delete_node(root->right, temp->data);
}
return root;
}
int main()
{
node *root = NULL;
/*create the following tree
95
/
55 110
/ /
40 75 100 150
*/
root = insert_node(root, 95);
insert_node(root, 55);
insert_node(root, 40);
insert_node(root, 75);
insert_node(root, 110);
insert_node(root, 100);
insert_node(root, 150);
cout << "\nIN ORDER :: ";
in_order(root);
cout << endl;
cout << "\nDeleting 40..." << endl;
root = delete_node(root, 40);
cout << "\nIN ORDER :: ";
in_order(root);
cout << endl;
return 0;
}
/*
OUTPUT
In-Order Traversal :: 40 55 75 95 100 110 150
Deleting 40...
40 not having degree 2 can't delete :(
In-Order Traversal :: 40 55 75 95 100 110 150
*/
This is a Program to Prevent Deletion of nodes having 0 or 1 degrees in the Binary Search Tree.
The approach will be as follow::
First, we will Construct the Binary Search Tree and insert some nodes
create the following tree
95
/
55 110
/ /
40 75 100 150
95
/
55 110
/ /
40 75 100 150
After Consrtucting this BST we can observe the nodes
0 Degree nodes -> 40, 75, 100, 150
1 Degree nodes -> No nodes
2 Degree nodes -> 95 55 110
So the Program is to prevent deletion of 0-degree or 1-degree nodes (i.e 40, 75, 100, 150 )
LOGIC::
we will check if the root's right child is NULL and the root's left child is NULL?
if yes then that node is having 0 degrees.
we will check if the root's right child is NULL or the root's left child is NULL?
if yes then that node is having 1 degree.
so don't perform deletion on both of these cases simply return by giving the message.
Here is the sample code for more clarification.
C++ CODE
using namespace std;
struct BST_node
{
int data;
struct BST_node *left, *right;
};
typedef struct BST_node node;
void in_order(node *root)
{
if (root)
{
in_order(root->left);
cout << root->data << " ";
in_order(root->right);
}
}
node *create_node(int d)
{
//create a new node
node *ptr = (node *)malloc(sizeof(node));
ptr->data = d;
ptr->right = ptr->left = NULL;
return ptr;
}
node *insert_node(node *root, int key)
{
//base case
if (!root)
return create_node(key);
//else recurse down the tree
if (key < root->data)
root->left = insert_node(root->left, key);
else
root->right = insert_node(root->right, key);
//if key is already present (root->data == key) then simply return the unchanged root
return root;
}
node *min_value(node *root)
{
node *current = root;
while (current && current->left != NULL)
current = current->left;
return current;
}
//this function delete the key and returns a new root
node *delete_node(node *root, int key)
{
//base condition
if (!root)
return root;
//------------------- locate the deletion --------------------------
//if key is less than it lies to lest sub tree else right sub tree
if (key < root->data)
root->left = delete_node(root->left, key);
else if (key > root->data)
root->right = delete_node(root->right, key);
else
{ //else the key is same as of root's key then this is the node is to be deleted
//case 1) if this node has 0 or 1 child
if (root->left == NULL)
{
cout << "\n"
<< root->data << " not having degree 2 can't delete :(" << endl;
return root;
}
else if (root->right == NULL)
{
cout << "\n"
<< root->data << " not having degree 2 can't delete :(" << endl;
return root;
}
//case 2) we reached here means root have 2 children so get the smallest from the right subtree
// (Means get the in-order successor)
node *temp = min_value(root->right);
//copy the in-order successor to this node
root->data = temp->data;
//now delete the in-order successor (temp)
root->right = delete_node(root->right, temp->data);
}
return root;
}
int main()
{
node *root = NULL;
/*create the following tree
95
/
55 110
/ /
40 75 100 150
*/
root = insert_node(root, 95);
insert_node(root, 55);
insert_node(root, 40);
insert_node(root, 75);
insert_node(root, 110);
insert_node(root, 100);
insert_node(root, 150);
cout << "\nIN ORDER :: ";
in_order(root);
cout << endl;
cout << "\nDeleting 40..." << endl;
root = delete_node(root, 40);
cout << "\nIN ORDER :: ";
in_order(root);
cout << endl;
return 0;
}
/*
OUTPUT
In-Order Traversal :: 40 55 75 95 100 110 150
Deleting 40...
40 not having degree 2 can't delete :(
In-Order Traversal :: 40 55 75 95 100 110 150
*/
Comments