C++ Program to prevent deletion of node having degree 2 in Binary Search Tree














































C++ Program to prevent deletion of node having degree 2 in Binary Search Tree



Description:
This is a Program to Prevent Deletion of nodes having 2 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 2 degrees nodes (i.e 95, 55, 110 )

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 perform deletion on both of these cases only.
else don't perform the deletion on the node simply return by giving the message.

Here is the sample code for more clarification.

C++ CODE 

//C++ program to Prevent deletion of node having degree 2 in Binary search tree

#include <bits/stdc++.h>
using namespace std;

struct binary_node
{
int data;
struct binary_node *left_child;
struct binary_node *right_child;
};

typedef binary_node NODE;

//Prototypes
NODE *create_new_node(int);
NODE *insert_node(NODE *, int);
NODE *delete_node(NODE *, int);

void in_order(NODE *);

int main()
{
//initially root node will be NULL
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);

//Display the tree
cout << "\nIn-Order Traversal :: ";
in_order(root);
cout << endl;

cout << "\nDeleting 95..." << endl;
root = delete_node(root, 95);

return 0;
}

NODE *insert_node(NODE *root, int key)
{
//base condition
if (!root)
return create_new_node(key);

//----------- locate insertion -----------------
if (key < root->data)
root->left_child = insert_node(root->left_child, key);
else
root->right_child = insert_node(root->right_child, key);

return root;
}

NODE *create_new_node(int key)
{
//create new node and return that node
NODE *new_node = (NODE *)malloc(sizeof(NODE));
new_node->data = key;
new_node->left_child = NULL;
new_node->right_child = NULL;

return new_node;
}

NODE *delete_node(NODE *root, int key)
{
//base case
if (!root)
return root;

// -------------- locate the deletion ------------------------
if (root->data < key)
root->left_child = delete_node(root->left_child, key);
else if (root->data > key)
root->right_child = delete_node(root->right_child, key);
else
{
//else the key is same as of root's key then this is the node is to be deleted
if (root->left_child == NULL)
{
NODE *temp_node = root->right_child;
free(root);
return temp_node;
}
else if (root->right_child == NULL)
{
NODE *temp_node = root->left_child;
free(root);
return temp_node;
}

//if the target node having degree 2
cout << "\n"
<< root->data << " having degree 2 can't delete :(" << endl;
}
return root;
}

void in_order(NODE *root)
{
if (root)
{
//in_order means left_child -> root -> right_child
in_order(root->left_child);
cout << root->data << " ";
in_order(root->right_child);
}
}

/*
OUTPUT

In-Order Traversal :: 40 55 75 95 100 110 150

Deleting 95...

95 having degree 2 :(
*/


More Articles of Anand Dasani:

Name Views Likes
C++ Program for OBST (Optimal Binary Search Tree) 4134 1
C++ Program for Matrix Chain Multiplication 3027 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 279 1

Comments