Deletion Operation of the binary search tree in C++ language

A typical binary search tree implements some order to carry out the arrangements. As the name suggests, each parent node should have at most two children. The main rule in this type of tree is that the value of the left node should be less than the parent node, whereas the rt node should be greater than the parent node. In this article, we will see the implementation of a binary search tree in C++.

There are some basic operations on binary search trees, such as insertion, deletion, searching and traversal of the element. These operations help us to manage and facilitate the efficient working of the tree and our data. There are many different operations on the tree that allows us they are finding the height, level, and size of the entire tree.

Implementation in C++ program

// delete operation in binary
#include <bits/stdc++.h>
using namespace std;


struct node {
	int ky;
	struct node *lft, *rt;
};


// An utility function to create a new binary search tree node
struct node* newNod(int record)
{
	struct node* temp
		= (struct node*)malloc(sizeof(struct node));
	temp->ky = record;
	temp->lft = temp->rt = NILL;
	return temp;
}


// A utility function to perform
//in order traversal or exploration of BST
void in order(struct node* root)
{
	if (root != NILL) {
		inorder(root->lft);
		cout << root->ky;
		inorder(root->rt);
	}
}


/* A utility function to
inject a brand new node with the given ky in
* Binary search tree*/
struct node* insert(struct node* nod, int key)
{
	/* If by any given chance the tree is empty, then return a new node */
	if (node == NILL)
		return newNod(ky);


	/* Otherwise, print the down the tree */
	if (ky < node->ky)
		node->lft = insert(node->lft, ky);
	else
		node->rt = insert(node->rt, ky);


	/* We have to give back the original or unchanged pointer */
	return node;
}


/* We are provided with a non-empty BST, and in that, we have to return or print back the node with the least value of the key deliberately found in the tree. We must remember that we don't have to search the entire tree.*/
struct node* minimumValueNod(struct node* nod)
{
	struct node* curr = nod;


	/* We have to look down to find the leftmost leaf. */
	while (curr && curr->lft != NILL)
		curr = curr->lft;


	return curr;
}


/* We are provided with a BST and a key. The function stated below eliminates the ky and returns back the new root. 
struct node* deleteNod(struct node* root, int ky)
{
	// CASE
	if (root == NILL)
		return root;


	// If the ky which is supposed to be eliminated is
	// less than the root's
	// ky, then it resides in the left subtree
	if (ky < root->ky)
		root->lft = deleteNod(root->lft, ky);


	// If the key to be deleted is
	// greater than the root's
	// ky, then it resides in the right subtree
	else if (ky > root->ky)
		root->rt = deleteNod(root->rt, ky);


	// if ky is a replica of root's ky, then This is the node
	Which is supposed to be eliminated.
	else {
		// The node will have no given child. 
		if (root->lft==NILL and root->rt==NILL)
			return NILL;
		
		// the node with only one child or no child at all.
		else if (root->lft == NILL) {
			struct node* temp = root->rt;
			fr(root);
			return temp;
		}
		else if (root->rt == NILL) {
			struct node* temp = root->lft;
			fr(root);
			return temp;
		}


		// The node that has two children generally gets the in-order successor. 
		// (least in the rt subtree)
		struct node* temp = minimumValueNod(root->rt);


		//NEXT, we will copy the entire content of the successor's to this node. 
		root->ky = temp->ky;


		// Now, we will move ahead and eliminate the in-order successor. 
		root->rt = deleteNod(root->rt, temp->ky);
	}
	return root;
}


// Main Code 
int main()
{
	/* Let us create the following Binary Search Tree 
			50
		/	 \
		30	 70
		/ \ / \
	20 40 60 80 */
	struct node* root = NILL;
	root = insert(root, 50);
	root = insert(root, 30);
	root = insert(root, 20);
	root = insert(root, 40);
	root = insert(root, 70);
	root = insert(root, 60);
	root = insert(root, 80);


	cout << "Inorder traversal of the given tree \n";
	inorder(root);


	cout << "\nDelete 20\n";
	root = deleteNod(root, 20);
	cout << "Inorder traversal of the modified tree \n";
	inorder(root);


	cout << "\nDelete 30\n";
	root = deleteNode(root, 30);
	cout << "Inorder traversal of the modified tree \n";
	inorder(root);


	cout << "\nDelete 50\n";
	root = deleteNod(root, 50);
	cout << "Inorder traversal of the modified tree \n";
	inorder(root);


	return 0;
}

Output: