450. Delete Node in a BST
1. Description
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.
2. Example
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: []
3. Constraints
- The number of nodes in the tree is in the range [0, $10^4$].
- $-10^5$ <= Node.val <= $10^5$
- Each node has a unique value.
- root is a valid binary search tree.
- $-10^5$ <= key <= $10^5$
4. Solutions
Iteration
n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
TreeNode *deleteNode(TreeNode *root, int key) {
TreeNode *guard = new TreeNode();
guard->left = root;
TreeNode *parent = guard;
while (root != nullptr && root->val != key) {
parent = root;
root = root->val < key ? root->right : root->left;
}
if(root == nullptr) {
return guard->left;
}
if (root->left == nullptr && root->right == nullptr) {
if (parent->left == root) {
parent->left = nullptr;
} else if (parent->right == root) {
parent->right = nullptr;
}
} else if (root->left == nullptr) {
if (parent->left == root) {
parent->left = root->right;
} else if (parent->right == root) {
parent->right = root->right;
}
} else if (root->right == nullptr) {
if (parent->left == root) {
parent->left = root->left;
} else if (parent->right == root) {
parent->right = root->left;
}
} else {
if (root->right->left == nullptr) {
root->val = root->right->val;
root->right = root->right->right;
} else {
TreeNode *node = root->right;
while (node->left->left != nullptr) {
node = node->left;
}
root->val = node->left->val;
node->left = node->left->right == nullptr ? nullptr : node->left->right;
}
}
return guard->left;
}
};