Binary Search TreesProblem 2 of 22
Deletion of a node in a BST
Problem Statement
Given a BST and a key, delete the node with the given key and return the root of the modified BST. The BST property must be maintained after deletion.
Example:
5 5
/ \ Delete 3 / \
3 6 --------> 4 6
/ \ \ / \
2 4 7 2 7
Input: root, key = 3
Output: Root of modified BST
Approach 1: Brute Force (Inorder Rebuild)
Intuition
Extract all nodes except the one to delete via inorder traversal (which gives sorted order), then rebuild a balanced BST from the sorted array.
Algorithm
- Perform inorder traversal to get sorted elements
- Skip the element to be deleted
- Rebuild BST from the sorted array
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private void inorder(TreeNode root, List<Integer> nodes, int key) {
if (root == null) return;
inorder(root.left, nodes, key);
if (root.val != key) nodes.add(root.val);
inorder(root.right, nodes, key);
}
private TreeNode buildBST(List<Integer> nodes, int left, int right) {
if (left > right) return null;
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(nodes.get(mid));
root.left = buildBST(nodes, left, mid - 1);
root.right = buildBST(nodes, mid + 1, right);
return root;
}
public TreeNode deleteNodeBruteForce(TreeNode root, int key) {
List<Integer> nodes = new ArrayList<>();
inorder(root, nodes, key);
if (nodes.isEmpty()) return null;
return buildBST(nodes, 0, nodes.size() - 1);
}
}Complexity Analysis
- Time Complexity: O(n) - Traversal + rebuild
- Space Complexity: O(n) - Storing all nodes
Approach 2: Optimal (In-place Deletion)
Intuition
Handle three cases based on the node to be deleted:
- Leaf node: Simply remove it
- One child: Replace node with its child
- Two children: Replace with inorder successor (or predecessor)
Algorithm
- Search for the node to delete using BST property
- If node has no children, return null
- If node has one child, return that child
- If node has two children:
- Find inorder successor (smallest in right subtree)
- Copy successor's value to current node
- Delete the successor from right subtree
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int findMin(TreeNode root) {
while (root.left != null) {
root = root.left;
}
return root.val;
}
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
// Search for the node
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
// Node found - handle three cases
// Case 1: Leaf node
if (root.left == null && root.right == null) {
return null;
}
// Case 2: One child
if (root.left == null) {
return root.right;
}
if (root.right == null) {
return root.left;
}
// Case 3: Two children
// Find inorder successor (min in right subtree)
int successorVal = findMin(root.right);
root.val = successorVal;
root.right = deleteNode(root.right, successorVal);
}
return root;
}
}Complexity Analysis
- Time Complexity: O(h) where h is height - O(log n) for balanced BST
- Space Complexity: O(h) - Recursion stack
Approach 3: Alternative (Using Predecessor)
Intuition
Instead of inorder successor, we can use inorder predecessor (largest in left subtree) for the two-children case.
Algorithm
- Find the node to delete
- For two children case, find max in left subtree (predecessor)
- Replace node's value with predecessor's value
- Delete predecessor from left subtree
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int findMax(TreeNode root) {
while (root.right != null) {
root = root.right;
}
return root.val;
}
public TreeNode deleteNodeUsingPredecessor(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) {
root.left = deleteNodeUsingPredecessor(root.left, key);
} else if (key > root.val) {
root.right = deleteNodeUsingPredecessor(root.right, key);
} else {
// Leaf node
if (root.left == null && root.right == null) {
return null;
}
// One child
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// Two children - use predecessor
int predecessorVal = findMax(root.left);
root.val = predecessorVal;
root.left = deleteNodeUsingPredecessor(root.left, predecessorVal);
}
return root;
}
}Complexity Analysis
- Time Complexity: O(h) where h is height
- Space Complexity: O(h) - Recursion stack
Key Takeaways
- Three cases: Leaf (easy), one child (replace), two children (use successor/predecessor)
- Inorder successor: Smallest element in right subtree
- Inorder predecessor: Largest element in left subtree
- BST property maintained: Successor/predecessor ensures ordering
- This is LeetCode #450 - Delete Node in a BST
- Deletion is more complex than insertion due to restructuring
- Both successor and predecessor approaches are valid