BST Delete (3 Cases)
Deleting a leaf, a node with one child, and a node with two children by copying the inorder successor. The most-asked BST exam question.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
Removing someone from an org chart. If they manage nobody, just remove them. If they manage one person, that person reports to their old boss. If they manage two teams, you need a replacement who fits between both teams. That is the whole idea.
First search for the node like normal. Then:
Case 1: a leaf (no children)
Just remove it. The parent’s pointer becomes nullptr.
Case 2: one child
Bypass it: the parent points directly to the node’s only child. The whole subtree moves up one level and the BST property still holds.
Case 3: two children
You cannot bypass a node with two children. Instead, find a value that can sit in its place: bigger than everything on the left, smaller than everything on the right. That is the inorder successor, the smallest value in the right subtree (go right once, then left until you can’t).
- Copy the successor’s value into the node.
- Delete the successor from the right subtree. It has no left child, so this is case 1 or 2.
(Using the inorder predecessor, the largest on the left, also works. Use whichever your instructor uses.)
Why the code is short
The recursive version returns the new root of each subtree. Cases 1 and 2 merge into one: “if there is no left child, return the right child (which may be nullptr)”.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Delete 20 (leaf), then 60 (one child), then 50 (two children). Watch 65 move up to the root.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
Node* insert(Node* root, int x) {
if (!root) return new Node{x, nullptr, nullptr};
if (x < root->data) root->left = insert(root->left, x);
else if (x > root->data) root->right = insert(root->right, x);
return root;
}
Node* findMin(Node* root) {
while (root->left != nullptr) root = root->left;
return root;
}
Node* remove(Node* root, int x) {
if (root == nullptr) return nullptr;
if (x < root->data) root->left = remove(root->left, x);
else if (x > root->data) root->right = remove(root->right, x);
else {
if (root->left == nullptr) { // case 1 (leaf) and case 2 (only right child)
Node* r = root->right; delete root; return r;
}
if (root->right == nullptr) { // case 2 (only left child)
Node* l = root->left; delete root; return l;
}
Node* s = findMin(root->right); // case 3: two children
root->data = s->data; // copy the inorder successor
root->right = remove(root->right, s->data);
}
return root;
}
void inorder(Node* r) { if (!r) return; inorder(r->left); cout << r->data << " "; inorder(r->right); }
void destroy(Node* r) { if (!r) return; destroy(r->left); destroy(r->right); delete r; }
int main() {
Node* root = nullptr;
for (int x : {50, 30, 70, 20, 40, 60, 80, 65, 35}) root = insert(root, x);
cout << "start: "; inorder(root); cout << "\n";
root = remove(root, 20); cout << "delete 20 (leaf): "; inorder(root); cout << "\n";
root = remove(root, 60); cout << "delete 60 (one child): "; inorder(root); cout << "\n";
root = remove(root, 50); cout << "delete 50 (two children): "; inorder(root); cout << "\n";
cout << "new root: " << root->data << "\n";
destroy(root);
}start: 20 30 35 40 50 60 65 70 80 delete 20 (leaf): 30 35 40 50 60 65 70 80 delete 60 (one child): 30 35 40 50 65 70 80 delete 50 (two children): 30 35 40 65 70 80 new root: 65
05Complexity
| delete, balanced | O(log n) |
|---|---|
| delete, skewed | O(n) |
| Extra space | O(h) recursion |
Case 3 walks down twice (to find the node, then to its successor), but both walks are on one path, so it is still O(h).
06Watch
Delete a node from Binary Search Tree
Why this one: Draws all three cases, then writes the recursive delete in C/C++. Exactly this page.
07Exam lens
Likely questions
- Explain the three cases of deleting a node from a BST, with a diagram for each.
- Delete 50 (the root) from the BST of 50, 30, 70, 20, 40, 60, 80. Draw the result.
- What is the inorder successor? Why does replacing with it keep the BST property?
- Write a recursive function to delete a node from a BST.
Common mistakes
- Case 3: copying the successor value but forgetting to delete the successor node itself (you get a duplicate).
- Case 3: searching for the successor in the left subtree. Successor = min of the right subtree.
- Not returning the new subtree root, so the parent still points at the deleted node.
- Forgetting
delete, or using the node after deleting it.
08Quick check
09Practice
🟢 Trace by hand
Build the BST from 50, 30, 70, 20, 40, 60, 80, 35, 45, 65. Delete 20, then 30, then 50. Draw the tree after each.
Show answer
- Delete 20 (leaf): 30's left becomes null.
- Delete 30: now 30 has only a right child (40), so case 2: 50's left becomes 40 (with 35 and 45 below it).
- Delete 50 (two children): successor = min of right = 60. Copy 60 to the root, then delete old 60 (case 2: 70's left becomes 65).
60
/ \
40 70
/ \ / \
35 45 65 80🟡 Implement it
Rewrite delete using the inorder predecessor (max of the left subtree) instead of the successor.
Hint
Swap findMin(root->right) for findMax(root->left), and recurse into root->left to remove it.
🔴 Solve problems
Hint
This page's
remove()function, using TreeNode.Hint
Inorder traversal with a counter. Stop when the counter reaches k.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.