4.Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference of the BST.

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.

2. If the node is found, delete the node.

Follow up: Can you solve it with time complexity O(height of tree)?

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.

Example 3:

Input: root = [], key = 0
Output: []

Approach :

Basically, the deletion can be divided into two stages:

• Search for a node to remove.

• If the node is found, delete the node.

Points where deletion can be done:

• Nodes having no child / leaf node.

             10                             10
           /     \         delete(5)      /     \
          7       15       --------->    7       15 
         /  \    /  \                     \     /  \ 
        5    8  11   18                    8   11   18
        
 Solution:- Connect the prev pointer to NULL 

• Nodes having only one child / one subtree.

             10                              10
           /     \         delete(15)      /     \
          7       15       --------->    7       11 
         /  \    /                      /  \      
        5    8  11                     5    8   
        
   Solution:- Connect the prev child to next child   

• Nodes having 2 child / two subtree.

             10                              11
           /     \         delete(10)      /     \
          7       15       --------->    7        15 
         /  \    /  \                   /  \        \ 
        5    8  11   18                5    8        18
        
 Solution:- 
 1. Find the Inorder Predecessor(Max elemet of left subtree) or 
 2. Inorder Successor (Min element of the right subtree)
 3. Replace with the Target node and delete the element.

Solution Iterative:

class Solution
{
public:

    //finding min(every subtree of a BST is a BST
    TreeNode *deleteNode(TreeNode *root, int key)
    {

        TreeNode *t = root;
        TreeNode *q = NULL;

        if (root == NULL)
        {
            return NULL;
        }

        while (t != NULL)
        {
            q = t;
            if (t->val > key)
            {
                t = t->left;
            }
            else if (t->val < key)
            {
                t = t->right;
            }

            if (t != NULL && t->val == key)
            {
                
                //case 1: no child;
                if (t->left == NULL && t->right == NULL)
                {
                    if (q != t) // Checking if the node to be deleted is not root
                    {
                        if (q->left == t)
                        {
                            q->left = NULL;
                        }
                        else
                        {
                            q->right = NULL;
                        }
                    }
                    else
                    {
                         root = NULL;
                    }
                }
                
                //case 2: one child;
                else if (t->left == NULL || t->right == NULL)
                {
                    TreeNode *next = NULL; // Fidning the next node
                    if (t->left != NULL)
                    {
                        next = t->left;
                    }
                    else
                    {
                        next = t->right;
                    }

                    if (q != t) // Checking if the node to be deleted is not root
                    {
                        if (q->left == t)
                        {
                            q->left = next;
                        }
                        else
                        {
                            q->right = next;
                        }
                    }
                    else
                    {
                        root = next;
                    }
                }
                
                //case 3: two child
                else
                {
                    TreeNode *temp;
                    TreeNode *p = NULL;
                    temp = t->right;
                    // Finding the inorder succesor (i.e min element of right sub tree)
                    while (temp->left != NULL)
                    {
                        p = temp;
                        temp = temp->left;
                    }

                    if (p != NULL) // Checking if the node to be deleted is not root
                    {
                        p->left = temp->right;
                    }
                    else
                    {
                        t->right = temp->right;
                    }

                    t->val = temp->val;
                }

                break;
            }
        }

        return root;
    }
};