# 450. 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.

Note: Time complexity should be O(height of tree).

Example:

``````root = [5,3,6,2,4,null,7]
key = 3

5
/ \
3   6
/ \   \
2   4   7

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 following BST.

5
/ \
4   6
/     \
2       7

5
/ \
2   6
\   \
4   7
``````

7
/ \
4   8
/   \
2     6
\   /
3 5

7
/ \
5   8
/   \
2     6
\
3

``````class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return NULL;
if (root->val > key) {
root->left = deleteNode(root->left, key);
} else if (root->val < key) {
root->right = deleteNode(root->right, key);
} else {
if (!root->left || !root->right) {
root = (root->left) ? root->left : root->right;
} else {
TreeNode *cur = root->right;
while (cur->left) cur = cur->left;
root->val = cur->val;
root->right = deleteNode(root->right, cur->val);
}
}
return root;
}
};
``````

``````class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return nullptr;
TreeNode *cur = root, *pre = nullptr;
while (cur) {
if (cur->val == key) break;
pre = cur;
if (cur->val > key) cur = cur->left;
else cur = cur->right;
}
if (!pre) return del(cur);
if (pre->left && pre->left->val == key) pre->left = del(cur);
else pre->right = del(cur);
return root;
}
TreeNode* del(TreeNode* node) {
if (!node) return nullptr;
if (!node->right) return node->left;
TreeNode *t = node->right;
while (t->left) t = t->left;
t->left = node->left;
return node->right;
}
};
``````

``````class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return NULL;
if (root->val == key) {
if (!root->right) return root->left;
else {
TreeNode *cur = root->right;
while (cur->left) cur = cur->left;
swap(root->val, cur->val);
}
}
root->left = deleteNode(root->left, key);
root->right = deleteNode(root->right, key);
return root;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/450

Split BST

https://leetcode.com/problems/delete-node-in-a-bst/

https://leetcode.com/problems/delete-node-in-a-bst/discuss/93296/Recursive-Easy-to-Understand-Java-Solution

https://leetcode.com/problems/delete-node-in-a-bst/discuss/93378/An-easy-understanding-O(h)-time-O(1)-space-Java-solution.

https://leetcode.com/problems/delete-node-in-a-bst/discuss/93331/concise-c-iterative-solution-and-recursive-solution-with-explanations

https://leetcode.com/problems/delete-node-in-a-bst/discuss/93293/Very-Concise-C%2B%2B-Solution-for-General-Binary-Tree-not-only-BST

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation