Deleting from a BST

Why it matters

Delete is the hardest of the three basic BST operations, and it is one of the most common BST questions in interviews. Insert and search only touch one path and then stop. Delete has to repair the tree after it removes a node, and the repair must keep the BST rule true for every value that remains. If you learn the three cases in this lesson, you can write delete in about fifteen lines and explain every line.

The lesson also covers freeing memory. Delete is the place where a C++ program gives memory back, so a bug here shows up as a crash or as a silently corrupted tree. You will see both kinds of bug, and you will learn how to spot them.

Start with an org chart

Picture a company where each manager has at most two people reporting to them. The managers are the nodes, and the reporting lines are the links. The rule of the company is that everyone on the left of a manager is ranked lower, and everyone on the right is ranked higher. That is the BST rule.

Now a manager leaves. What happens to the people below them? There are three situations.

If the manager has nobody reporting to them, you just remove the box from the chart. Nobody needs to move. This is the easy case.

If the manager has exactly one person below them, that person moves up into the manager's place. The ranking still works, because everyone below that person was already on the correct side.

If the manager has two people below them, you cannot move both into one box. You need a replacement who fits between the left group and the right group. The natural choice is the person who ranks just above the manager, which is the lowest person in the right group. That person moves into the manager's place, and then you remove that person's old box from the right group.

That last idea is the whole secret of BST delete. The rest of this lesson turns it into code.

The rule for the replacement

In a BST, the value that sits just above a node is the inorder successor. It is the smallest value that is larger than the node. Inside a tree, you find it like this: if the node has a right subtree, the successor is the smallest value in that subtree, which is its leftmost node. You will see this in the code.

Why does the successor keep the rule true? Suppose the node holds 50, and its successor is 60. Every value in the left subtree of 50 is smaller than 50, so it is also smaller than 60. Every value in the right subtree of 50 is at least 60, because 60 is the smallest of them. So if we copy 60 into the node's place, the left side is still smaller, and the right side is still larger. The rule holds, and the copy of 60 in the right subtree is now a duplicate that we must remove.

The inorder predecessor works the same way from the other side. It is the largest value in the left subtree. You can use either one. This lesson uses the successor, and practice exercise 1 asks you to switch to the predecessor.

The three cases

Delete always starts with a search for the value. Once you find the node, act on how many children it has.

Case 1: no children (a leaf). Remove the node. The parent's link becomes nullptr. Nothing else moves.

Case 2: one child. Replace the node with its child. The child's whole subtree moves up one level. The order is still valid, because that subtree was already on the correct side of the parent.

Case 3: two children. Find the successor, which is the leftmost node of the right subtree. Copy its value into the node you are deleting. Then delete the successor from the right subtree. The successor has no left child, because it is the smallest value on that side. So the second delete is always case 1 or case 2, never case 3.

Three rows showing a leaf, a one-child node and a two-child node before and after a delete

Look at the bottom row of the picture. The root holds 50, with 30 on the left and 70 on the right. The node 70 has a left child 60, which is the successor. After the delete, 60 sits at the root. Its old place under 70 is gone, and 70 keeps only its right child 80.

The code

Here is the complete erase function, followed by the rest of the program. The insert function and the inorder function are the same as in lesson 1.

The output is:

start:             1 3 4 6 7 8 10 13 14 
after deleting 3:  1 4 6 7 8 10 13 14 
after deleting 1:  4 6 7 8 10 13 14 
after deleting 14: 4 6 7 8 10 13 
after deleting 8:  4 6 7 10 13 
new root value: 10

Read the output carefully. After every delete, the inorder walk is still sorted, and the value you removed is gone. That is the test every delete must pass: the output is sorted, and the set of values is the old set minus one.

Trace the two-child delete

Start with the tree from lesson 1. We delete 3, which has two children: the left child 1 and the right child 6.

The erase function first searches for 3. It starts at 8. Three is smaller than 8, so the call goes left with root->left = erase(root->left, 3). At node 3, the key matches, so the code reaches the else branch. Node 3 has both children, so neither if fires.

The code finds the successor with minNode(root->right). The right subtree of 3 is the tree rooted at 6. Its leftmost node is 4, so succ points at the node holding 4.

Next, root->val = succ->val; copies 4 into the node that holds 3. Now that node says 4, and it still has left child 1 and right child 6. The value 3 is gone from the tree at this point, but a copy of 4 is in two places.

Finally, root->right = erase(root->right, succ->val); removes the old 4. The call starts at 6. Four is smaller, so the call goes left to the node holding 4. That node is a leaf, so its branch deletes it and returns nullptr. The node 6 stores nullptr as its left link.

The result is a tree whose inorder walk is 1 4 6 7 8 10 13 14. Each value appears once, and the order is right.

Trace the root delete

The last delete removes 8, the root. It has two children, so it is case 3 again. By this point the tree is 8 with left subtree 4 (with right child 6, which has right child 7) and right subtree 10 (with right child 13). The right subtree has no left child at its top, so its leftmost node is 10 itself. The successor is 10.

Copy 10 into the root. The root object stays where it is, and only its value changes to 10. Then erase 10 from the right subtree. That node has no left child, so it is case 2, and its right child 13 moves up into the link. The root's right link now points at 13.

The output says the new root value is 10. The number at the root changed, but the root object is the same one that existed before the delete. Only the value inside it was replaced. The node that was freed is the old successor node.

Notice the function prints the root value after the delete. The root can change on every delete, so the code must always store the return value back into root in main. That is why the line is root = erase(root, 8); and not erase(root, 8);.

Why each case reconnects the tree

Look again at the three recursive calls in the code:

root->left = erase(root->left, key);
root->right = erase(root->right, key);
root->right = erase(root->right, succ->val);

Each call returns the subtree that should now sit in that link. The call may return the same node, a different node, or nullptr. Assigning the result back is what makes the change visible to the parent. If you forget the assignment, the parent keeps the old link. For a leaf, that old link now points at freed memory, which is the bug the next section shows.

Step through the recursive erase below for the two-child delete of 3. Watch the calls go down until they reach the node, then watch each caller store the subtree it gets back.

The first two cases share code. When the left child is nullptr, the function returns the right child. If the right child is also nullptr, the function returns nullptr, which is correct for a leaf. If the right child exists, it moves up, which is correct for a node with only a right child. The second if handles the mirror case: only a left child, so return the left child.

The same operations, driven by commands

Real programs rarely call delete from fixed code. They read a list of commands, one per line, and apply each one in order. This program does that. The first number says how many commands follow. Each command is one of three letters. I followed by a number inserts it. D followed by a number deletes it. P prints the whole tree in sorted order, or prints empty if the tree has no nodes.

The main function does not change. It reads one command at a time, calls the matching function, and stores the root back in the variable, because delete can change the root.

Type this into the Input box:

8
I 5
I 3
I 8
I 1
D 3
P
D 5
P

The output is:

1 5 8 
1 8 

Here is the story. The first four commands build the tree 5 with left subtree 3 (whose left child is 1) and right child 8. The command D 3 removes a node with one child, so 1 moves up and the tree becomes 5 with left child 1 and right child 8. The first P prints 1 5 8. The command D 5 removes the root, which has two children. Its successor is 8, so the root takes the value 8 and the old 8 leaf is removed. The second P prints 1 8.

Change the input to 1 followed by P and the output is empty. Try your own list of commands. Predict the output on paper first, then run it. A wrong prediction tells you which case you misunderstood.

The predecessor version

Practice exercise 1 asks you to switch from the successor to the predecessor. The idea is a mirror image. The predecessor is the largest value in the left subtree, found by walking right. The code below uses it in case 3. It is otherwise the same as the successor version.

The output is:

after deleting 8: 1 3 4 6 7 10 13 14 
new root value: 7
after deleting 3: 1 4 6 7 10 13 14 

The predecessor of 8 is 7, which is the largest value in the left subtree. So the root takes the value 7. Both versions give a valid BST. They can produce different shapes, so if you compare the output of the two versions, compare the inorder walk and not the root.

Work one delete all the way through

Before you trust the code, follow one delete by hand. Use a very small tree: 5 at the root, with 2 as its left child and 8 as its right child. It has three values, so you can check every step on paper.

Delete 5, which is the root with two children.

Step 1: the search starts at the root, and the root holds 5. The key matches at once, so there is nothing to search past.

Step 2: the node has two children, so it is case 3. The successor is the smallest value in the right subtree. The right subtree holds only 8, so the successor is 8.

Step 3: copy 8 into the root. The root now holds 8. Its left child is still 2. Its right child is still the old node that holds 8, which is the node you must now remove.

Step 4: delete 8 from the right subtree. The recursive call starts at that right child, which holds 8, so the key matches at once. The node has no children, so it is case 1. The call frees the node and returns nullptr, and the root's right link becomes nullptr.

The result is a root holding 8, with 2 as its only child. The inorder walk prints 2 8. The root changed from 5 to 8, which is why main must store the returned root.

Now delete 2 from that tree. The node 2 is a leaf under the root, so case 1 applies. The root's left link becomes nullptr, and only 8 is left. Two deletes, two cases, and each step matched one line of the code.

Deleting a value that is not there

Walk the search for 99 in the nine-value tree from this lesson. The search starts at 8. Ninety-nine is larger than 8, so the call goes right to 10. Ninety-nine is larger than 10, so the call goes right to 14. Ninety-nine is larger than 14, so the call goes right to the right child of 14, which is nullptr.

The base case if (!root) return nullptr; returns nullptr. Node 14 stores that value in its right link, which was already nullptr. Node 10 stores its right link again, which is still 14. Node 8 stores its right link again, which is still 10. Nothing changed, and no node was freed. The inorder walk after the call prints the same list as before.

The same thing happens on an empty tree. The first call returns nullptr at once, and main stores nullptr back into root. This is why the base case matters more than it looks. Without it, the first line that reads root->val would crash on a null pointer, and exit code 139 would tell you nothing about the cause.

Sometimes a program must know whether a delete changed anything. The usual fix is a flag. Pass a bool& into erase, set it to true only at the line that frees a node, and read the flag in main. Practice exercise 3 asks you to explain this case, and the flag is a small change to the function you already have.

Freeing memory: children first

delete root gives the node's memory back to the heap. After that line, the pointer root still holds the old address, but the memory there can be reused by the next new. Reading or writing through that pointer is a bug, and the program may crash, print garbage, or quietly work until later.

Freeing a whole tree needs an order. You must free the children before the parent, because the parent holds the only pointers to its children. If you free the parent first, you cannot find the children anymore. This order is called postorder: visit the left subtree, then the right subtree, then the node.

This program frees a tree and counts the nodes it frees.

The output is:

freed 9 nodes

Look at the line int count = freeAll(n->left);. It reads n->left before the node is deleted. The line delete n; comes after both recursive calls, so n->left and n->right were already read. Nothing reads n after the delete. This is the safe order.

After freeAll returns, root still holds the old address, so the program sets it to nullptr. Setting the pointer to nullptr after a free is a habit that prevents accidental use later.

Common mistakes and what the tools show

Each mistake in this section compiles, or nearly does, which makes it dangerous. The messages below are real. Your addresses will be different, but the wording will be the same.

Mistake 1: forgetting to reconnect the child. If you write erase(root->left, key); without storing the return value, a leaf delete frees the node and leaves its parent pointing at it. Reading that parent later reads freed memory. Compile with the address sanitizer, which is a tool that checks memory use at run time, and you see this:

ERROR: AddressSanitizer: heap-use-after-free on address 0x7917651e0050 at pc 0x5e1367a8a451
READ of size 8 at 0x7917651e0050 thread T0
    #0 0x5e1367a8a450 in eraseBad(Node*, int) .../bad6.cpp:9

The line #0 names the function and the line where the bad read happened. The address and the other numbers change each run. The words heap-use-after-free tell you what went wrong. The bad program in this example had the mistake delete root; return root->right;, which reads after the delete. The same error appears whenever you touch a node after deleting it.

Compile with g++ -std=c++17 -g -fsanitize=address when you test delete code. The sanitizer is slower, but it catches these bugs on the first run, which saves a lot of time.

Mistake 2: using the wrong key in case 3. After copying the successor's value, the next delete must remove the successor's value from the right subtree. If you pass key instead, the function looks for the value you originally asked to delete. That value is no longer in the right subtree, so nothing is removed, and the successor's value now appears twice. Here is the output of the broken version, which deletes 8 from the tree of lesson 1:

1 3 4 6 7 10 10 13 14 

The two 10s are the clue. The tree is still sorted, but a value appears twice. Put the right key in the call, erase(root->right, succ->val), and the duplicate goes away. This kind of bug is hard to see if you only print the root. Print the whole inorder walk after every delete.

Mistake 3: forgetting that the root can change. The root is a pointer, and deleting the root returns a new root. If main ignores the return value, the old root pointer now refers to freed memory. Always write root = erase(root, key);.

Mistake 4: deleting a missing key. The base case if (!root) return nullptr; handles a key that is not in the tree. The search reaches a nullptr link, returns it, and the parent stores the same nullptr. Nothing changes. This is the behaviour you want, but only if the base case exists. Without it, the function reads root->val on a null pointer, which crashes with exit code 139.

Mistake 5: searching for the successor on the left side. The successor is in the right subtree. Going left finds a value smaller than the node, which breaks the rule. If the code shows wrong order after a two-child delete, check which subtree you searched.

Mistake 6: leaking memory. A program that never calls delete keeps every node until it exits. The operating system reclaims the memory when the program ends, so short programs seem fine. A long-running server that inserts and deletes all day slowly eats memory. The sanitizer reports leaks at exit with the message LeakSanitizer: detected memory leaks, followed by the size of the leak. The fix is to call delete in the erase function, as this lesson does.

Debugging walkthrough: a tree that looks wrong after delete

Imagine a learner who writes erase, tests it on the same tree, and gets the output with two 10s. The learner does not know which delete caused it, so they add one print after each delete, and the trace shows the first wrong line.

The method is simple. Print the whole tree after each operation, not only the root. Read the output from the top. The first line that breaks the rule or repeats a value is the first wrong step. Then reread the code for that case only.

For a two-child delete, check these four things in order:

1. Did the search find the right node?
2. Did the code pick the leftmost node of the right subtree?
3. Did the copy go into the node you are deleting?
4. Did the second delete use the successor's value?

The third and fourth checks catch most bugs. If the copy goes into the wrong node, the tree breaks the rule. If the second delete uses the wrong key, the value stays twice.

Variations and edge cases

Deleting the only node. The root has no children, so case 1 returns nullptr. The root in main becomes nullptr, which represents an empty tree. Insert and search handle that. Min and max do not, because they read root->left immediately. Check for nullptr before calling them.

Deleting a missing key. The function returns the tree unchanged. Some programs want to report that the key was missing. Add a bool parameter that the function sets to true when it deletes something.

Deleting every value. After enough deletes, the root becomes nullptr. Deleting from an empty tree is safe, because the base case returns nullptr.

Predecessor instead of successor. Both choices keep the BST rule. Practice exercise 1 asks you to write the predecessor version.

Height after delete. Deleting can make a tree taller or shorter. Deleting a node from a chain makes the chain shorter by one level. Deleting from a balanced tree can make one side taller than the other, which is why balanced trees need extra work after delete. Lesson 5 covers that repair.

Duplicates. If duplicates are allowed and placed on the right, a delete must remove one copy, and the rule for which copy to remove must match the insert rule. This module ignores duplicates, so delete never has to choose.

Complexity

Delete does two searches. The first finds the node, which costs O(h). The second finds the successor, which costs at most O(h) more. The second delete is a smaller search in the right subtree, so the total is still O(h).

On a balanced tree with a million values, h is about 20, so delete takes about 40 steps at most. On a chain of a million values, it can take a million steps.

What happens inside: the call stack and the links

The recursive erase uses the call stack the same way insert does. Each level of the tree adds one frame, so the extra memory is O(h). The frame holds root and key, and when the call returns, the parent stores the answer into its link.

Think of the links as the only way to reach the tree. When erase deletes a node, the parent's link is changed to point at something else, or to nullptr. The old node has no links that point to it anymore, so it is safe to free, as long as nothing else still points at it. In a plain BST, only the parent points at each node, so this is safe. Some other structures keep extra pointers, and they need more care.

When case 3 copies a value, the node object stays put, and only its val field changes. The successor's node is the object that goes away. That is why the code reads succ->val after root->val has changed: the successor's node still has its value until the second erase frees it.

Interview questions and real-world use

Expect a question like "Delete a node from a BST." Start by stating the three cases. Then write the search, then the cases, in that order. Say the complexity is O(h). If the interviewer asks about the cost in the worst case, say O(n), and name the balanced trees from lesson 5 as the fix.

A strong whiteboard answer follows the same order as the code. Say the rule first: search for the value, then look at the number of children. Draw the three cases with small trees, not large ones, because a three-node example is enough to show each case. For case 3, explain why the successor keeps the order. The successor is larger than everything in the left subtree, because the whole node was larger than its left side. It is smaller than everything else in the right subtree, because it is the smallest value there. Then write the function, and check it by hand on a three-node tree before you say it is finished. Interviewers often follow up with "what if the successor itself has a child?" The answer is that it cannot have a left child, so the second delete is case 1 or case 2.

A harder follow-up is "Delete without copying values." The answer uses a pointer to the parent link, which lets you replace the successor node itself instead of its value. This is the version that matters when the node carries other data, because copying a whole record can be expensive. Practice exercise 9 gives you the code, and exercise 10 gives the proof.

Real code uses delete in ordered containers all the time. Removing a key from std::set or std::map runs the same three cases, inside the library. You will not write that code in your daily work, but knowing it lets you read the source and understand the cost.

Practice

Try these before you open the solutions. Compile your code with g++ -std=c++17 -Wall -g -fsanitize=address so that the sanitizer checks your memory use.

1. Easy. Rewrite case 3 so that it uses the inorder predecessor instead of the successor. Hint: the predecessor is the largest value in the left subtree.

Node* maxNode(Node* n) {
    while (n->right) n = n->right;
    return n;
}
 
// Inside erase, replace the two-child branch with this:
Node* pred = maxNode(root->left);
root->val = pred->val;
root->left = erase(root->left, pred->val);

2. Easy. Write void freeTree(Node* root) that frees every node. Hint: free the children before the parent.

void freeTree(Node* root) {
    if (!root) return;
    freeTree(root->left);
    freeTree(root->right);
    delete root;
}

3. Easy. Delete the value 99 from the nine-node tree in the lesson, which does not contain 99. Describe exactly what happens.

4. Medium. Write Node* eraseMin(Node* root) that removes the smallest value. Hint: the smallest node has no left child, so you can return its right child to its parent.

Node* eraseMin(Node* root) {
    if (!root) return nullptr;
    if (!root->left) {
        Node* r = root->right;
        delete root;
        return r;
    }
    root->left = eraseMin(root->left);
    return root;
}

5. Medium. Write Node* deleteGreater(Node* root, int x) that removes every value larger than x and returns the new root. Hint: if the root is larger than x, the whole right subtree is larger too, so you can drop it all.

void freeTree(Node* root) {
    if (!root) return;
    freeTree(root->left);
    freeTree(root->right);
    delete root;
}
 
Node* deleteGreater(Node* root, int x) {
    if (!root) return nullptr;
    if (root->val > x) {
        Node* keep = deleteGreater(root->left, x);   // the left side may still hold small values
        freeTree(root->right);                       // everything on the right is larger than x
        delete root;
        return keep;
    }
    root->right = deleteGreater(root->right, x);     // the root stays, so check the right side
    return root;
}

6. Medium. Start with the tree 4 with left child 2 (which has children 1 and 3) and right child 6 (which has children 5 and 7). Delete 4. Draw the result.

7. Medium. Explain why the successor of a node with two children never has a left child.

8. Medium. Write a function Node* eraseRange(Node* root, int lo, int hi) that removes every value from lo to hi, inclusive. Hint: you may call erase in a loop, once for each value that is in the range.

void collectRange(Node* n, int lo, int hi, vector<int>& out) {
    if (!n) return;
    if (n->val > lo) collectRange(n->left, lo, hi, out);
    if (n->val >= lo && n->val <= hi) out.push_back(n->val);
    if (n->val < hi) collectRange(n->right, lo, hi, out);
}
 
Node* eraseRange(Node* root, int lo, int hi) {
    vector<int> doomed;
    collectRange(root, lo, hi, doomed);
    for (int v : doomed) root = erase(root, v);
    return root;
}

9. Hard. Write Node* eraseNoCopy(Node* root, int key) that deletes the node by relinking pointers, without copying values. Hint: in case 3, find the successor and its parent, then move the successor node into the deleted node's position.

Node* eraseNoCopy(Node* root, int key) {
    if (!root) return nullptr;
    if (key < root->val) {
        root->left = eraseNoCopy(root->left, key);
        return root;
    }
    if (key > root->val) {
        root->right = eraseNoCopy(root->right, key);
        return root;
    }
    if (!root->left) {
        Node* r = root->right;
        delete root;
        return r;
    }
    if (!root->right) {
        Node* l = root->left;
        delete root;
        return l;
    }
    // Two children: find the successor and detach it.
    Node* parent = root;
    Node* succ = root->right;
    while (succ->left) {
        parent = succ;
        succ = succ->left;
    }
    if (parent != root) parent->left = succ->right;   // the successor's right child moves up
    else parent->right = succ->right;
    succ->left = root->left;                          // the successor takes over the children
    succ->right = (parent == root) ? succ->right : root->right;
    delete root;
    return succ;
}

10. Hard. Prove that after copying the successor into a two-child node, the second delete can never reach case 3. Explain in a short paragraph.

What you now know

• Delete starts with a search, then acts on the number of children: none, one, or two.
• Case 3 copies the inorder successor into the node and deletes the successor from the right subtree.
• The successor never has a left child, so the second delete is always case 1 or case 2.
• Each recursive call returns the subtree that must sit in its link, and the parent must store it.
• Free a tree in postorder, children before the parent, and never read a node after you delete it.
• Use the address sanitizer to catch use-after-free and leak bugs, and print the whole inorder walk after each delete.

The next lesson asks whether a tree is a valid BST, which is harder than it looks, and shows how to find the successor of any value.