---
# System prepended metadata

title: LC 450. Delete Node in a BST
tags: [medium, leedcode, BST, python]

---

# 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<sup>4</sup>]</code>.
- <code>-10<sup>5</sup> <= Node.val <= 10<sup>5</sup></code>
- Each node has a  **unique**  value.
- <code>root</code> is a valid binary search tree.
- <code>-10<sup>5</sup> <= key <= 10<sup>5</sup></code>


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

## Solution 1
#### Python
```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++
```cpp=
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
```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 - 
![](https://i.imgur.com/jH64vNJ.gif)

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