 ### C++ Program to prevent deletion of node having degree 0 or 1 in Binary Search Tree

Description:
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
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

#include <bits/stdc++.h>
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
*/ #### More Articles of Anand Dasani:

Name Views Likes
C++ Program for OBST (Optimal Binary Search Tree) 4135 1
C++ Program for Matrix Chain Multiplication 3028 1
C++ Program for Huffman Code 3601 1
C++ Program for 8 Queen problem 2794 1
C++ Program for KnapSack Problem TopDown Solution 576 1
C++ Program for KnapSack Problem Memoization Solution 722 1
C++ Program for KnapSack Problem Recursive Solution 629 1
C++ Program for Tower Of Hanoi problem 507 1
C++ Program to Evaluate the Postfix string using stack 439 1
C++ Program to check Balanced Parenthesis in string using stack 447 1
C++ Program for String Palindrome check using stack 2997 1
C++ Program to Convert Infix Expression to Prefix Expression including Parenthesis 337 1
C++ Program To Convert Infix Expression to Prefix Expression without Parenthesis 663 1
C++ PROGRAM TO CONVERT INFIX EXPRESSION TO POSTFIX EXPRESSION WITHOUT PARENTHESIS 333 1
C++ Program to Convert Infix Expression to Postfix Expression including Parenthesis 357 1
C++ Program to Convert Decimal Value to Hexa Decimal using Stack 798 1
C++ Program to Convert Decimal Value to Octal using Stack 983 1
C++ Program to Convert Decimal Value to Binary using Stack 612 1
C++ Program for Upper Triangular Matrix 587 1
C++ Program for Lower Triangular Matrix 317 1
C++ Program for Diagonal Matrix 465 1
C++ Program to Perform Full Deletion operation in BST 278 1
C++ Program to count the nodes having Degree 2 in BST 649 1
C++ Program to count the nodes having 1 Degree in BST 482 1
C++ Program to count the nodes having 0 Degree in BST 338 1
C++ Program to count the Height of Binary Search Tree 299 1
C++ Program to prevent deletion of node having degree 2 in Binary Search Tree 261 2
C++ Program to prevent deletion of node having degree 0 or 1 in Binary Search Tree 280 1