
Description
The problem involves deleting a node with a specified key from a binary search tree (BST). The task is to find the node with the given key and remove it from the tree while maintaining the properties of a BST. The key considerations include handling cases where the node to be deleted has no children, one child, or two children.
Intuition
When deleting a node from a BST, the structure and properties of the tree must be preserved. The complexity arises when the node to be deleted has two children. The most intuitive solution involves finding either the minimum value in the right subtree or the maximum value in the left subtree (inorder successor or predecessor) to replace the deleted node.
Approach
- Traverse the Tree: Begin by locating the node to be deleted by traversing the tree from the root.
- Handle Deletion Cases: - Leaf Node: If the node has no children, simply remove it. - Single Child: If the node has one child, replace the node with its child. - Two Children: If the node has two children, find the minimum value in the right subtree (inorder successor), replace the node's value with this minimum value, and recursively delete the inorder successor.
- Recursive Deletion: Implement the solution recursively, adjusting pointers to maintain the BST structure.
Complexity
Time Complexity:
The time complexity is O(h), where h
is the height of the tree. In the worst case, this could be O(n) for a skewed tree.
Space Complexity:
The space complexity is O(h) due to the recursive call stack, which in the worst case could also be O(n).
Code
C++
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return nullptr;
if (key < root->val) {
root->left = deleteNode(root->left, key);
} else if (key > root->val) {
root->right = deleteNode(root->right, key);
} else {
if (!root->left && !root->right) return nullptr;
if (!root->left) return root->right;
if (!root->right) return root->left;
root->val = findMin(root->right);
root->right = deleteNode(root->right, root->val);
}
return root;
}
private:
int findMin(TreeNode* root) {
while (root->left) {
root = root->left;
}
return root->val;
}
};
Python
class Solution:
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
if not root:
return None
if key < root.val:
root.left = self.deleteNode(root.left, key)
elif key > root.val:
root.right = self.deleteNode(root.right, key)
else:
if not root.left and not root.right:
return None
if not root.left:
return root.right
if not root.right:
return root.left
root.val = self.findMin(root.right)
root.right = self.deleteNode(root.right, root.val)
return root
def findMin(self, root: TreeNode) -> int:
while root.left:
root = root.left
return root.val
Java
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
if (root.left == null && root.right == null) return null;
if (root.left == null) return root.right;
if (root.right == null) return root.left;
root.val = findMin(root.right);
root.right = deleteNode(root.right, root.val);
}
return root;
}
private int findMin(TreeNode root) {
while (root.left != null) {
root = root.left;
}
return root.val;
}
}
JavaScript
var deleteNode = function (root, key) {
function removeNode(root, key) {
if (root == null) return null;
if (key < root.val) {
root.left = removeNode(root.left, key);
}
else if (key > root.val) {
root.right = removeNode(root.right, key);
}
else {
if (!root.left && !root.right) return null;
if (!root.left) return root.right;
if (!root.right) return root.left;
root.val = min(root.right);
root.right = removeNode(root.right, root.val);
}
return root;
}
return removeNode(root, key)
};
function min(root) {
if (!root.left) return root.val;
return min(root.left);
}