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: Search for a node to remove. If the node is found, delete the node.
Approach 1:
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return root; // If the tree is empty
}
TreeNode parent = null;
TreeNode curr = root;
// Step 1: Find the node to be deleted
while (curr != null && curr.val != key) {
parent = curr;
if (key < curr.val) {
curr = curr.left;
} else {
curr = curr.right;
}
}
if (curr == null) {
return root; // Node with the key not found
}
// Step 2: Delete the node
// Case 1: Node to be deleted has no children (leaf node)
if (curr.left == null && curr.right == null) {
if (curr != root) {
if (parent.left == curr) {
parent.left = null;
} else {
parent.right = null;
}
} else {
root = null;
}
}
// Case 2: Node to be deleted has two children
else if (curr.left != null && curr.right != null) {
TreeNode successor = getMinimumKey(curr.right);
int val = successor.val;
deleteNode(root, successor.val);
curr.val = val;
}
// Case 3: Node to be deleted has only one child
else {
TreeNode child = (curr.left != null) ? curr.left : curr.right;
if (curr != root) {
if (curr == parent.left) {
parent.left = child;
} else {
parent.right = child;
}
} else {
root = child;
}
}
return root;
}
private TreeNode getMinimumKey(TreeNode curr) {
while (curr.left != null) {
curr = curr.left;
}
return curr;
}
}
Time Complexity: O(n) and Space Complexity: O(n)
The "Delete Node in a Binary Search Tree (BST)" problem involves removing a node from a BST while ensuring the tree remains a valid BST. Deleting a node in a BST is more complex than in a regular binary tree due to the specific properties of a BST, where for each node, the left subtree contains smaller elements, and the right subtree contains larger elements.
The task is to delete a node with a given value and adjust the tree structure to maintain the BST properties.
Problem Statement
Given the root of a binary search tree and a key to be deleted, delete the node with the given key. After the deletion, return the root of the modified BST. It is guaranteed that the node to be deleted exists in the tree.
The tree node structure is given above. The task is to delete the node with the specified key and return the updated tree's root.
Approach
To delete a node in a BST, we need to consider three different cases:
- If the node to be deleted has no children (leaf node), we simply remove the node.
- If the node to be deleted has one child, we remove the node and replace it with its single child (either the left or right child).
- If the node to be deleted has two children, we need to find the in-order successor (the smallest node in the right subtree) or in-order predecessor (the largest node in the left subtree). We replace the value of the node to be deleted with the in-order successor's value and recursively delete the in-order successor.
The goal is to ensure that after deletion, the tree remains a valid BST.
Algorithm
The algorithm can be broken down as follows:
- If the root is None, return None.
- If the node to be deleted is smaller than the current node's value, recursively attempt to delete the node in the left subtree.
- If the node to be deleted is larger than the current node's value, recursively attempt to delete the node in the right subtree.
- If the node to be deleted is found, check the three cases:
- If the node has no children, return None to remove the node.
- If the node has one child, return that child to replace the node.
- If the node has two children, find the in-order successor or predecessor, replace the node’s value with the in-order successor’s value, and recursively delete the in-order successor.
- Return the updated root after deletion.
Example
Consider the following Binary Search Tree:
5
/ \
3 8
/ \ / \
2 4 6 9
If we want to delete the node with value 3, the resulting tree will look like:
5
/ \
4 8
/ / \
2 6 9
After deleting 3, we replace it with its in-order successor, which is 4. The tree is still a valid BST.
Time Complexity
The time complexity of deleting a node in a BST is O(h), where h is the height of the tree. In the worst case (unbalanced tree), the height can be O(n), where n is the number of nodes in the tree. In the best case (balanced tree), the height is O(log n).
The space complexity is O(h) due to the recursion stack. In the worst case (unbalanced tree), the space complexity can be O(n), but in the best case (balanced tree), it is O(log n).
Optimized Approach
The current solution is quite efficient, as it performs the necessary steps to delete a node in a BST while maintaining the tree's properties. The main optimization potential is in the tree’s balance. If the tree is unbalanced, the performance can degrade to O(n). Techniques like AVL trees or Red-Black trees can help ensure that the tree remains balanced, but they involve more complexity and overhead.
Time Complexity (Optimized)
The time complexity remains O(h), where h is the height of the tree, and space complexity remains O(h), where h is the height of the tree due to the recursion stack. If the tree is balanced, both time and space complexities become O(log n).
Conclusion
The "Delete Node in a Binary Search Tree" problem demonstrates how to carefully handle three different cases of node deletion to ensure the BST properties are preserved. The solution is efficient, with a time complexity of O(h) and space complexity of O(h). For unbalanced trees, maintaining balance would require additional techniques, but the basic approach remains optimal for most cases.
