# 6.3 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.

Chapter: Trees · ~45 min · hard
URL: https://dsa.fetehadin.com/learn/bst-delete

## Mental 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).

1. Copy the successor's value into the node.
2. 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`)".

## C++ code: bst-delete.cpp

```cpp
#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);
}
```

Expected output:

```text
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
```

## Complexity

| Case | Cost |
| --- | --- |
| delete, balanced | O(log n) |
| delete, skewed | O(n) |

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)**.

## Videos

- [Delete a node from Binary Search Tree](https://youtu.be/gcULXE7ViZw) (mycodeschool): Draws all three cases, then writes the recursive delete in C/C++. Exactly this page.

## Exam 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.

## Quick check

1. Deleting a node with **one** child means…
   A. delete its whole subtree
   B. connect its parent directly to its child
   C. replace it with the root
   D. it cannot be deleted
   Answer: B. The child (with its subtree) moves up one level.

2. The inorder successor of a node with two children is…
   A. its left child
   B. the max of its left subtree
   C. the min of its right subtree
   D. its parent
   Answer: C. Go right once, then left as far as possible.

3. BST 50, 30, 70, 60, 80, 65. After deleting 50, the root is…
   A. 30
   B. 60
   C. 65
   D. 70
   Answer: B. The min of the right subtree (70 → 60) is 60. Its value is copied to the root, then the old 60 node is removed (65 moves up into its place).

4. Can the inorder successor (in case 3) have a left child?
   A. Yes, always
   B. No; it is the leftmost node of that subtree, so its own removal is case 1 or 2
   C. Only in skewed trees
   D. Only if it is a leaf
   Answer: B. That is why the recursive call to remove it is easy.

## Practice

**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.

Solution:

- 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).

```text
        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.

**Problems:**

- [Delete Node in a BST](https://leetcode.com/problems/delete-node-in-a-bst/) (medium). Hint: This page's `remove()` function, using TreeNode.
- [Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/) (medium). Hint: Inorder traversal with a counter. Stop when the counter reaches k.

## Mastery checklist

- [ ] I can delete a leaf from a BST.
- [ ] I can delete a node with one child.
- [ ] I can delete a node with two children using the inorder successor.
- [ ] I can write the recursive delete function from memory.