[link](https://leetcode.com/problems/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:

Search for a node to remove.
If the node is found, delete the node.

#### 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: []

#### Constraints:

- The number of nodes in the tree is in the range [0, 104].
- -105 <= Node.val <= 105
- Each node has a unique value.
- root is a valid binary search tree.
- -105 <= key <= 105

---

The code first checks if the root is None, indicating an empty tree. In that case, it returns None. If the root is not None, it compares the key with the root.val to determine the location of the node to be deleted.

If key is greater than root.val, the code recursively calls the deleteNode function on the right subtree, updating root.right with the returned subtree. If key is less than root.val, the code recursively calls the function on the left subtree, updating root.left with the returned subtree.

If key is equal to root.val, it handles three cases:

If the node to be deleted has no left child, it returns the right child, effectively removing the node.

If the node to be deleted has no right child, it returns the left child, effectively removing the node.

If the node to be deleted has both left and right children, it finds the minimum node in the right subtree (the smallest value greater than the current node). It replaces the value of the node to be deleted with the value of the minimum node, and recursively deletes the minimum node from the right subtree.

Finally, the code returns the modified root node after the deletion.

#### Solution 1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None

        if key > root.val:
            root.right = self.deleteNode(root.right, key)
        elif key < root.val:
            root.left = self.deleteNode(root.left, key)
        else:
            if not root.right:
                return root.left
            elif not root.left:
                return root.right

            # find the minimum node
            cur = root.right
            while cur and cur.left:
                cur = cur.left
            root.val = cur.val
            root.right = self.deleteNode(root.right, root.val)

        return root
        

O(T): O(logN)
O(S): O(logN)