DSA
Delete Node in a BST
Recursive BST Deletion (Inor… approach. Optimal — Time O(h), Space O(h).
Problem: LeetCode 450
Difficulty: Medium
Topic: BST, Recursion
Problem Summary#
Given the root of a BST and a key, delete the node with that key and return the updated root. The BST property must be maintained after deletion.
Approach: Recursive BST Deletion (Inorder Successor)#
Intuition: Deletion in a BST has three cases depending on the node being deleted:
- No left child → replace node with its right child
- No right child → replace node with its left child
- Two children → can't simply remove it. Instead, find the inorder successor (leftmost node in the right subtree — the smallest value greater than the current node), copy its value into the current node, then delete the successor from the right subtree. This maintains BST ordering with minimal restructuring.
BST search property is used to navigate to the target node: go right if key > root->val, left if key < root->val.
class Solution {
public:
// Returns the inorder successor: leftmost node in the right subtree
TreeNode* succ(TreeNode* root) {
root = root->right;
while (root && root->left)
root = root->left;
return root;
}
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return root;
if (root->val < key)
root->right = deleteNode(root->right, key); // go right
else if (root->val > key)
root->left = deleteNode(root->left, key); // go left
else {
// Found the node to delete
if (!root->left) {
TreeNode* curr = root->right;
delete root;
return curr; // case 1: no left child
}
else if (!root->right) {
TreeNode* curr = root->left;
delete root;
return curr; // case 2: no right child
}
else {
TreeNode* suc = succ(root); // case 3: two children
root->val = suc->val; // overwrite with successor's value
root->right = deleteNode(root->right, suc->val); // delete successor
}
}
return root;
}
};
Complexity#
| Time | O(h) — search + successor find, h = tree height |
| Space | O(h) — recursion stack depth |
h = O(log n) for balanced BST, O(n) worst case (skewed tree).
Deletion Cases Illustrated#
Case 1 — no left child: Case 2 — no right child:
5 5
/ \ delete 7 / \ delete 3
3 7 --------> 3 7 -------->
\ /
9 2
5 5
/ \ / \
3 9 2 7
Case 3 — two children:
5
/ \
3 8 delete 5
/ \ -------->
6 9
6
/ \
3 8
\
9
In case 3: successor of 5 is 6 (leftmost node in the right subtree — descend from 8 to its left child 6, which itself has no left child). Copy 6 → root, then delete 6 from the right subtree; since 6 is a leaf, it's simply detached, leaving 8 with only its right child 9.
Notes#
- The successor approach is chosen over the predecessor (rightmost in left subtree) — either works equally well.
- root->val = suc->val avoids pointer rewiring; only the value is swapped, then the duplicate in the right subtree is deleted recursively.
- delete root is called in cases 1 and 2 to free memory — good practice though LeetCode doesn't require it.