# LC 450. Delete Node in a BST

### [Problem link](https://leetcode.com/problems/delete-node-in-a-bst/)

###### tags: `leedcode` `python` `medium` `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:**
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/04/del_node_1.jpg" style="width: 800px; height: 214px;" />

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.
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/04/del_node_supp.jpg" style="width: 350px; height: 255px;" />

**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 <code>[0, 10⁴]</code>.
- <code>-10⁵ <= Node.val <= 10⁵</code>
- Each node has a **unique** value.
- <code>root</code> is a valid binary search tree.
- <code>-10⁵ <= key <= 10⁵</code>

**Follow up:** Could you solve it with time complexity <code>O(height of tree)</code>?

## Solution 1
#### Python

# 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 root.val < key:
            root.right = self.deleteNode(root.right, key)
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        else:
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            node = root.right # find minimum of right tree
            while node.left:
                node = node.left
            node.left = root.left
            root = root.right

        return root

#### C++

class Solution {
public:
    TreeNode *findMax(TreeNode *node) {
        while (node->right != nullptr) {
            node = node->right;
        }
        return node;
    }

    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) {
            return root;
        }
        if (root->val == key) {
            if (root->left == nullptr && root->right == nullptr) {
                delete root;
                return nullptr;
            } else if (root->left == nullptr || root->right == nullptr) {
                TreeNode *node = nullptr;
                if (root->left == nullptr) {
                    node = root->right;
                } else {
                    node = root->left;
                }
                delete root;
                return node;
            } else {
                TreeNode *cur = findMax(root->left);
                cur->right = root->right;
                TreeNode *tmp = root;
                root = root->left;
                delete tmp;
                return root;
            }
        }
        if (key > root->val) {
            root->right = deleteNode(root->right, key);
        }
        if (key < root->val) {
            root->left = deleteNode(root->left, key);
        }
        return root;
    }
};

## Solution 2
#### Python

# 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 root

        if root.val == key:
            if not root.right:  # 第一次交換後在這裡進行第二次交換, 把key設成None
                return root.left
            tmp = root.right
            while tmp.left:
                tmp = tmp.left
            root.val, tmp.val = tmp.val, root.val   # 第一次交換

        root.left = self.deleteNode(root.left, key)
        root.right = self.deleteNode(root.right, key)

        return root

>### Complexity
>n = The number of nodes in the tree.
>h = Height of tree.
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(h) | O(n) |
>| Solution 2 | O(n) | O(n) |

## Note
[reference](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0450.%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.md)

solution1 -

solution2 -
對於普通二叉樹都通用的刪除方式（沒有使用BST的性質, 而是遍歷整棵樹），用交換val的來刪除目標節點。
>第一次是和目標節點右子樹最左節點(右子樹中最小)交換.
>第二次把目標節點設成None.