Dare2Solve
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.
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.
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.
The space complexity is O(h) due to the recursive call stack, which in the worst case could also be O(n).
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;
}
};
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
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;
}
}
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);
}