Added case to delete the root node of the BST, Modified function FindMin to handle deletion from both right and left subtree. Added flag variable to judge if root node has to be deleted

BSTDeletion_CPP.cpp

/* Deleting a node from Binary search tree */
#include<iostream>
using namespace std;
struct Node {
	int data;
	struct Node *left;
	struct Node *right;
};
//Function to find minimum in a tree. 
// Changes by Paras Starts
Node* FindMin(Node* root, data)
{
	// This modification will help to determine from which side of the tree the node is being deletd and 
	// based on that respective traversing will be initiated.
	// If we are deleting node from the right subtree (data > root->data) then we need to find the node in left side of 
	//the Right subtree. If we are deleting node from left subtree (data < root->data) then we need to find node in right side
	//of the left subtree
	if(data < root.data){
		while(root->left != NULL) root = root-> right
	}
	else {
		while(root->left != NULL) root = root->left;
	}
	return root;
	// Changes by Paras Ends
}

// Function to search a delete a value from tree.
struct Node* Delete(struct Node *root, int data, flag) {
	if(root == NULL) return root; 
	else if(data < root->data){
		flag = false;
		root->left = Delete(root->left,data, flag);
	} 
	else if (data > root->data){
		flag = false;
		root->right = Delete(root->right,data, flag);
	} 
	// Changes by Paras Starts
	else if(data == root-> data && flag){
		temp = root;
		newRoot = root->left;
		root = root->left;
		// Move current root to the end of right most node of the left subtree
		while(root->right != Null){
			root = root->right;
		}
		
		root->right = temp->right;
		delete temp, root;
		return newRoot;
	}
	// Changes by Paras Ends
	// Wohoo... I found you, Get ready to be deleted	
	else {
		// Case 1:  No child
		if(root->left == NULL && root->right == NULL) { 
			delete root;
			root = NULL;
		}
		//Case 2: One child 
		else if(root->left == NULL) {
			struct Node *temp = root;
			root = root->right;
			delete temp;
		}
		else if(root->right == NULL) {
			struct Node *temp = root;
			root = root->left;
			delete temp;
		}
		// case 3: 2 children
		else { 
			struct Node *temp = FindMin(root->right, data);
			root->data = temp->data;
			root->right = Delete(root->right,temp->data, flag);
		}
	}
	return root;
}
 
//Function to visit nodes in Inorder
void Inorder(Node *root) {
	if(root == NULL) return;
 
	Inorder(root->left);       //Visit left subtree
	printf("%d ",root->data);  //Print data
	Inorder(root->right);      // Visit right subtree
}
 
// Function to Insert Node in a Binary Search Tree
Node* Insert(Node *root,char data) {
	if(root == NULL) {
		root = new Node();
		root->data = data;
		root->left = root->right = NULL;
	}
	else if(data <= root->data)
		root->left = Insert(root->left,data);
	else 
		root->right = Insert(root->right,data);
	return root;
}

int main() {
	/*Code To Test the logic
	  Creating an example tree
	                    5
			   / \
			  3   10
			 / \   \
			1   4   11
    */
	Node* root = NULL;
	root = Insert(root,5); root = Insert(root,10);
	root = Insert(root,3); root = Insert(root,4); 
	root = Insert(root,1); root = Insert(root,11);
	// Changes by Paras Starts
	// This flag variable is to judge if node being deleted is the root node.
	flag = True

	// Deleting node with value 5, change this value to test other cases
	root = Delete(root,5, flag);
	// Changes by Paras Ends

	//Print Nodes in Inorder
	cout<<"Inorder: ";
	Inorder(root);
	cout<<"\n";
}