# 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 (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:**

![](https://assets.leetcode.com/uploads/2020/09/04/del_node_1.jpg)

```
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.**  

```cpp
             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.** 

```cpp
             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.**

```cpp
             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:

```cpp
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;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://soumyajit4419.gitbook.io/ds-algo/binary-search-tree/delete-node-in-a-bst.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.