In this article, we will discuss deleting a node from a given binary search tree. Before we delete a node, we have to know what kind of node is it. A BST can have three types of nodes:

  1. Node with no child, i.e., leaf node. We simply remove this kind of node from the tree—for example, 20.

  1. Node with one child: We replace this node with its child node (left or right). For example, 50

  1. Node with two children: We replace its contents with a minimum value in its right subtree or maximum value in its left subtree for this kind of node. And delete that minVal/maxVal node.

This can also be rephrased as replacing the contents of the node to be deleted with the inorder successor (node that comes just after the node to be deleted in the inorder traversal), which will be the minimum value in the right subtree or replacing contents of the node to be deleted with the inorder predecessor (node that comes just before the node to be deleted in the inorder traversal) which will be the maximum value in the left subtree — and deleting the inorder successor/predecessor node after; for example, 100.

CODE:

#include 
#include 
using namespace std;

class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = right = NULL;
}
};

void inorder(TreeNode* root){
if(!root) return;
inorder(root->left);
coutleft = insert(root->left, val);
    else
        root->right = insert(root->right, val);
    return root;
}

TreeNode* minValueNode(TreeNode* root){
TreeNode* temp = root;
while(temp->left)
temp = temp->left;
return temp;
}
TreeNode* deleteTreeNode(TreeNode* root, int val){
if (root == NULL)
        return root;

    if (val < root->val)
        root->left = deleteTreeNode(root->left, val);

    else if (val > root->val)
        root->right = deleteTreeNode(root->right, val);

    else {
        if (root->left == NULL && root->right == NULL)
            return NULL;

        else if (root->left == NULL) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }

    TreeNode* temp = minValueNode(root->right);
    root->val = temp->val;
    root->right = deleteTreeNode(root->right, temp->val);
    }
    return root;

}
int main()
{
/* Let us create the following BST
              100
           /     \
          50      150
         /  \    /  \
       20   80  120   180 */
    TreeNode* root = NULL;
    root = insert(root, 100);
    root = insert(root, 50);
    root = insert(root, 150);
    root = insert(root, 20);
    root = insert(root, 80);
    root = insert(root, 120);
    root = insert(root, 180);

    cout&lt;&lt;"Initially the tree is \n";
    inorder(root);

    cout&lt;&lt;"\n\nDeleting 20......\n";
    root = deleteTreeNode(root,20);
    cout&lt;&lt;"Tree after deleting\n";
    inorder(root);

    cout&lt;&lt;"\n\nDeleting 50.....\n";
    root = deleteTreeNode(root,50);
    cout&lt;&lt;"Tree after deleting\n";
    inorder(root);

    cout&lt;&lt;"\n\nDeleting 100.....\n";
    root = deleteTreeNode(root,100);
    cout&lt;&lt;"Tree after deleting\n";
    inorder(root);

    return 0;
}

OUTPUT:
Initially, the tree is
20 50 80 100 120 150 180

Deleting 20......
Tree after deleting. 50 80 100 120 150 180

Deleting 50.....
Tree after deleting. 80 100 120 150 180

Deleting 100.....
Tree after deleting
80 120 150 180

Time complexity (T.C.): In the worst case, we might have to travel to the deepest node of the tree, so T.C. is O(h), where h is the height of the BST. For skewed BST, the height will be n, so the T.C. will be O(n).