BST Deletion · ITC 120

Part 1 · The problem

Why deleting is harder

Think of the officers of a purok, drawn as a chart: the Kapitan on top, each leader with the people under them. When a leader leaves, someone must fix the chart so that nobody under that leader gets left out. What we do depends on how many are under the leader:

Three situations, three fixes. Deleting from a BST works the same way, with one more rule: the values must stay in order.

Deleting from a BST

Deleting a value from a binary search tree means taking that value out of the tree, so that every other value stays in the tree and the BST rule still holds. Usually the node that holds it is removed. When that node has two children (Part 4), it stays and gets the next value instead, and the node that held the next value is removed.

Here are the words this lesson uses, in plain terms:

Word	In plain words
The node to delete	The node that holds the value we remove (red in the pictures).
Its children	The nodes right below it: zero, one, or two. This number decides the case.
Its parent	The node right above it. The parent's link is what we change.
The next value	The value that comes right after it in sorted order. Only case 3 needs it (Part 4).

What you already know

We use the BST rule and the starting BST again. In-order (L, N, R) lists a BST from smallest to largest:

10 20 30 40 50 60 70

From the Recursion lesson, insertRec saves what each call returns . Deletion uses the same pattern.

Why not just remove it?

Inserting always adds a leaf at the bottom. Deleting can remove a node from the middle. If we just remove 20, what happens to 10 and 30?

before: just remove 20?

→after

after: 10 and 30 are cut off

They are cut off from the tree. So after a delete, two things must stay true:

Every remaining node is still connected.
The BST rule still holds.

Where you see this

Deleting a contact from your phone: the list must stay sorted, and no other contact may disappear.

The three cases

First, always find the node, the same way as BST search: smaller, go left; larger, go right. Then, what we do depends on how many children it has:

Case	What we do
1. No children (a leaf)	Just remove it.
2. One child	The child moves up into its place.
3. Two children	Both children cannot move up into one spot. So we keep the node's spot and put a different value in it: the next value. Part 4 shows how.

Try it: tap each node below and see which case it would be.

Which case?

Tap any node to see what deleting it would be.

Tap a node. Red = the node to delete; gold = the child that moves up; yellow = its two children.

Part 2 · Case 1

Delete a leaf

Delete 10. Find it: 10 < 40, go left. 10 < 20, go left. Found. 10 has no children. Nothing hangs below it, so we just remove it. Its parent's link becomes null:

before: delete 10 (a leaf)

→after

after: 20's left is null

Check

Every other node is still connected, and the BST rule still holds. In-order: 20 30 40 50 60 70.

In the purok chart, this is Liza leaving : nobody is under her, so nothing else changes.

Part 3 · Case 2

Delete a node with one child

Here, 45 was added under 50, so 50 has one child. Delete 50. Find it: 50 > 40, go right. 50 < 60, go left. Found. Its only child, 45, moves up into 50's place: 60's left is now 45.

before: delete 50 (one child)

→after

after: 60's left is 45

Why this is safe

45 was already in 60's left subtree, so 45 < 60. Moving it up keeps the BST rule.

Like deleting from a linked list

In the Linked Lists lesson, to delete a node, the node before it skips it: its next now points to the node after it. Case 2 works the same way. 50 sits between 60 and 45, like a node in a chain:

After deleting, 60 skips 50 and points straight to 45. In the tree, that means 60's left is now 45.

What if 45 has children?

They come along. The whole subtree under 45 moves up together, unchanged:

before: delete 50

→after

after: 45, 42, 48 moved up together

This is Joy moving up into Ben's place : her own members stay with her.

Part 4 · Case 3

Delete a node with two children

Delete 20. It has two children, 10 and 30. In case 2, the only child moved up. Here there are two children, but only one spot.

The trick

Do not remove 20's spot. Keep it, and just change the value inside it. Then the tree's shape stays connected. Like Rosa's post in the purok chart: the post stays, someone else fills it.

Which value fits in 20's spot?

Here is our starting BST again, with its sorted list (in-order) below it. The dotted lines show that each node sits right above its place in the list:

Find 20 in the list. The box right after it is 30. That is the value we want: the next value. 30 fits in 20's spot because it is:

bigger than everything on 20's left (10), and
the smallest value on 20's right.

Next value (in-order successor)

The next value after a node is the smallest value that is bigger than it. Textbooks and other formal references call it the in-order successor. Both names mean the same thing.

Finding the next value in the tree

In a big tree, writing the whole sorted list is slow. This rule finds the next value in the tree itself:

The rule

Go right once. Then go left, left, left… until there is no left child.

This works when the node has a right child, which is always true for a node with two children.

A bigger BST (45, 42, 48 added). Next value after 40: right once (60), then left, left, left (50, 45, 42). 42 has no left child, so stop: 42. Check: 10 20 30 40 42 45 48 50 60 70.

Your turn: tap any node to see its next value.

Find the next value

Tap a node. Teal = the path (right once, then left); gold = the next value.

Tap a node with a right child, like 20, 45, or 60.

Why the rule works

The next value after 40 is the smallest value that is bigger than 40. The two steps find exactly that:

Right once: everything bigger than 40 is on its right side (yellow).
Left, left, left: smaller values are on the left, so the node farthest left (42) is the smallest of them.

Same rule, any tree

For 20 in the starting BST: right once to 30. 30 has no left child, so "left, left, left" is zero steps. The next value is 30, the box right after 20 in the sorted list .

Delete 20, step by step

Now we put it together. Go through the five steps:

Delete 20 (case 3)

Use Next to go through the steps.

Step 1. Find 20. 20 < 40, so go left. Found. It has two children: case 3.

Step 1 of 5

Another example: delete the root, 40

The root works the same way. Try predicting each step before you tap Next:

Delete 40 (case 3, the root)

Use Next to go through the steps.

Step 1. Find 40. 40 is the root, so we find it right away. It has two children: case 3.

Step 1 of 5

Two notes on case 3

Removing the next value is always easy

We stop going left only when there is no left child. So the node holding the next value never has a left child. It has either no children (case 1) or only a right child (case 2). It never has two, so we never get stuck in case 3 again.

Here 55 was added. 50 is still the next value after 40. It has no left child, only a right child (55), so removing it is case 2.

Another valid way

Some books use the largest value on the left instead (the in-order predecessor). That also keeps the BST rule. In this course, we use the next value (successor).

Quick check

Use the starting BST . Answer on scratch paper first.

To delete 30, which case is it?
To delete 60, what is the next value?

Check your answers

Case 1. 30 is a leaf. Just remove it: 20's right becomes null.
70. Right once from 60 → 70. 70 has no left child, so stop. 70 is copied into 60's spot, and the old 70 is removed.

Part 5 · Watch it

All three cases in the lab

Try each example in order. Then type your own values to delete from the same tree (tap Reset tree to start again).

Deletion lab

Red = the node to delete. Gold = the child or next value that moves. Orange = a spot that got a new value.

Try an example

Color key

to delete moves / next value new value in this spot path

Part 6 · In code

`deleteRec` in Java

deleteRec is our own method. It follows the same pattern as insertRec . This table compares them:

Same as `insertRec`	New in `deleteRec`
First, it looks for the value, like BST search: smaller, look left; larger, look right. To look, it calls itself.	When the value is found, it does what you did by hand: remove a leaf, move up the only child, or copy in the next value.
When a call finishes, it gives back a node. The call above saves it as its left or right child.	If the value is not in the tree, nothing changes.
At the end, each call usually gives back its own node.	Cases 1 and 2 give back the node that takes this node's place (or `null`, if nothing does).

A first look at the whole method

Just skim it first. You do not need to understand every line yet; the walkthroughs below explain each part. The colors match the parts of the method:

not foundsearch (calls itself)found: cases 1 and 2case 3 (calls itself once more)

 1static TreeNode deleteRec(TreeNode node,
 2                          int value) {
 3  if (node == null) {                            // not found
 4    return null;
 5  }
 6  if (value < node.data) {                       // search
 7    node.left = deleteRec(node.left, value);
 8  } else if (value > node.data) {
 9    node.right = deleteRec(node.right, value);
10  } else {
11    // found it
12    if (node.left == null) {                     // case 1, 2
13      return node.right;
14    }
15    if (node.right == null) {
16      return node.left;
17    }
18    TreeNode successor = node.right;             // case 3
19    while (successor.left != null) {
20      successor = successor.left;
21    }
22    node.data = successor.data;
23    node.right = deleteRec(node.right,
24                           successor.data);
25  }
26  return node;
27}

Is it recursive?

Yes. Like insertRec, deleteRec calls itself (lines 7, 9, and 23). It stops when the value is not found, or in cases 1 and 2.

The two inputs: `node` and `value`

node: the node this call is looking at.
value: the number we want to delete.

To delete 20 from the whole tree, we type root = deleteRec(root, 20); Yes, we type the word root: it is our variable that points to the top node, 40. We pass root, not 40, because deleteRec needs a node, not a number. While searching, each new call gets a different node (one step down) but the same value.

Some lines use Java you may not have read aloud yet. Here is how to say them:

Line	Read it aloud as
`return node.right;` (13)	"Give back my right child, so it takes my place."
`TreeNode successor = node.right;` (18)	"Make a new variable, successor, that starts at my right child." (Right once.)
`while (successor.left != null)` (19)	"While successor still has a left child…" (then line 20 moves it left)
`node.data = successor.data;` (22)	"Copy the next value into my spot."

successor is a name we chose, from "in-order successor." Any variable name would work.

Finding the node (lines 3–10)

 3  if (node == null) {
 4    return null;
 5  }
 6  if (value < node.data) {
 7    node.left = deleteRec(node.left, value);
 8  } else if (value > node.data) {
 9    node.right = deleteRec(node.right, value);
10  } else {

Blue, lines 6–9: exactly like insertRec. Go left or right, and save what the call returns.
Green, lines 3–5: we reached an empty spot, so the value is not in the tree. Return null: the empty spot stays empty. Nothing is deleted.
Yellow, line 10: else means the value is neither smaller nor larger: we found it.

Cases 1 and 2 in code: delete 50

When we find the node, its call returns the node that should take its place. The parent's call saves it at line 7 or 9. Walk through deleting 50 from the case 2 tree :

Code walkthrough: deleteRec(root, 50)

Tap any line to see what it does, or use Next to go through the code in order.

Call stack (newest on top)

call for 40running

node → 40value = 50

We type root = deleteRec(root, 50); The first call gets node → 40 (the root) and value = 50. "Call for 40" is our name for the call whose node points to 40.

Step 1 of 12

 1static TreeNode deleteRec(TreeNode node, 2                          int value) { 3  if (node == null) {                            // not found 4    return null; 5  } 6  if (value < node.data) {                       // search 7    node.left = deleteRec(node.left, value); 8  } else if (value > node.data) { 9    node.right = deleteRec(node.right, value);10  } else {11    // found it12    if (node.left == null) {                     // case 1, 213      return node.right;14    }15    if (node.right == null) {16      return node.left;17    }18    TreeNode successor = node.right;             // case 319    while (successor.left != null) {20      successor = successor.left;21    }22    node.data = successor.data;23    node.right = deleteRec(node.right,24                           successor.data);25  }26  return node;27}

The key step, in the call for 60

In node.left = deleteRec(node.left, value); the right side of = finishes first and gives back 45. Then the left side, node.left =, stores it. 60's left is now 45, so 50 is cut out.

Where is case 1?

A leaf has no children, so its left and right are both null. Line 12 is true, so line 13 returns node.right. But the right is null too, so the call returns null. The parent saves null, and the leaf is gone. So case 1 needs no extra code.

Case 3 in code: delete 20

Lines 18–24 do the five steps of deleting 20 by hand : find the next value, copy it, then remove the old copy with one more call.

Code walkthrough: deleteRec(root, 20)

Tap any line to see what it does, or use Next to go through the code in order.

Call stack (newest on top)

call for 40running

node → 40value = 20

We type root = deleteRec(root, 20); The first call: node → 40, value = 20.

Step 1 of 12

 1static TreeNode deleteRec(TreeNode node, 2                          int value) { 3  if (node == null) {                            // not found 4    return null; 5  } 6  if (value < node.data) {                       // search 7    node.left = deleteRec(node.left, value); 8  } else if (value > node.data) { 9    node.right = deleteRec(node.right, value);10  } else {11    // found it12    if (node.left == null) {                     // case 1, 213      return node.right;14    }15    if (node.right == null) {16      return node.left;17    }18    TreeNode successor = node.right;             // case 319    while (successor.left != null) {20      successor = successor.left;21    }22    node.data = successor.data;23    node.right = deleteRec(node.right,24                           successor.data);25  }26  return node;27}

When the next value has a child

Here, 50 has a right child, 55. Delete 40. The next value is 50. Line 22 copies 50 into the root. Then line 23 makes a new call with value = 50 to remove the old 50:

This line runs: node.right = deleteRec(node.right, successor.data);

before: 50 copied into the root

→after

after: old 50 removed (case 2)

The old 50 has one child, 55: case 2. That call returns 55, and the call for 60 saves it at line 7. The next value never has a left child, but it can have a right child.

Why `root =` matters

Always call it like this: root = deleteRec(root, value); Sometimes the root itself changes. Delete 20 from this small tree:

This line runs: root = deleteRec(root, 20);

before: root is 20

→after

after: root is 30

20 has one child (case 2), so the call returns 30. root = saves it, and 30 becomes the new root.

Compare with insertion

In insertion, root = mattered for the empty tree. In deletion, it matters whenever the root is removed and a child takes its place. If you forget root =, root still points to the old 20.

Special situations

Two more situations can happen. Both are handled by the code you already saw; no extra lines are needed:

Situation	What happens
Delete the only node	It is a leaf, so the call returns `null`. `root =` saves it: the tree is now empty.
Delete a value that is not in the tree (or from an empty tree)	The search reaches an empty spot. Lines 3–4 return `null`, the empty spot stays empty, and every call above saves its same child again. Nothing changes.

Part 7 · Watch out

Three common mistakes

For each mistake, read the situation, look at the picture, then read the fix.

Mistake 1 · search: not saving the result

The situation: a student writes the search line without node.left =, then deletes 10:

if (value < node.data) {
  deleteRec(node.left, value);        // result not saved
}

The buggy line runs: deleteRec(node.left, value);

before: delete 10

→after

after: 10 is still there

What went wrong: the call for 10 returns null, but nobody saves it. 20's left still points to 10, so 10 is not deleted.

The fix: node.left = deleteRec(node.left, value); Compare with a correct case 1 .

Mistake 2 · case 3: forgetting to remove the next value

The situation: this version copies the next value (line 22) but skips lines 23–24, then deletes 20:

TreeNode successor = node.right;
while (successor.left != null) {
  successor = successor.left;
}
node.data = successor.data;
// lines 23-24 are missing

The buggy line runs: node.data = successor.data;

before: delete 20

→after

after: 30 appears twice

✗ In-order10 30 30 40 50 60 70

✓ Right in-order10 30 40 50 60 70

What went wrong: after deleting 20, the value 30 appears twice.

The fix: always remove the next value after copying it: node.right = deleteRec(node.right, successor.data);

Mistake 3 · case 3: using the right child as the next value

The situation: to delete 40, someone copies its right child, 60, without going left. Then the old 60 is removed (its next value, 70, takes its place):

// "the next value is just the right child"
node.data = node.right.data;
node.right = deleteRec(node.right, node.right.data);

The buggy line runs: node.data = node.right.data;

before: delete 40

→after

after: 50 is on the wrong side

✗ In-order10 20 30 60 50 70

✓ Right in-order10 20 30 50 60 70

What went wrong: the root is now 60, but 50 is in its right subtree, and 50 < 60. The BST rule is broken, and the in-order list is no longer sorted.

The fix: right once, then left as far as you can. For 40, the next value is 50.

Part 8 · Your turn

Try it yourself

Do these on scratch paper. Problems 1, 2, and 4 start from the starting BST; problem 3 has 65 added. The coding task at the end runs in Java.

Delete 70. Which case? Draw the result.
Delete 60. What is the next value? Draw the result, or build it below.

Build the tree after deleting 60

Drag a value onto a dashed spot. On a phone, you can also tap a value, then tap a spot. Tap a leaf to take it back.

From this tree (65 added), delete 70. Which case? Draw the result.
Using deleteRec, we delete 30 from the starting BST. In the call for 30, which line returns, and what does it return? Which line saves it, and in which node?
Fill in the four blanks for case 3. The comment at the end of each line (A to D) names its blank:

TreeNode successor = node.______;   // A
while (successor.______ != null) {  // B
  successor = successor.left;
}
node.data = ______;                 // C
node.right = deleteRec(node.right,
                       ______);     // D

Show the answer key (for self-study, not for grading)

Case 1 (a leaf). 60's right becomes null.
Next value: 70 (right once, no left child). 70 is copied into 60's spot, and the old 70 is removed.
Case 2 (one child, 65). 65 moves up: 60's right is now 65.
30 is a leaf. Its left is null, so line 13 returns node.right, which is null. Back in the call for 20, line 9 saves it: 20's right becomes null.
A: right · B: left · C: successor.data · D: successor.data

Your coding task: delete the smallest value

At the registrar's window, the lowest queue number is served first, then it leaves the line. A BST can do the same job: find the smallest value, then delete it. Where is the smallest value? Start at the root and keep going left until a node has no left child.

Before you code, think: which of the three cases can that node be? (The answer is in the reveal.)

Write deleteMin in about 7 lines where it says YOUR CODE. It is recursive, like insertRec and deleteRec: each call gives back a node, and the call above saves it. main uses the starting BST with 15 added under 10, shown below. It deletes the smallest value twice, then deletes from a small tree whose root is the smallest. Run it: each printed line must match its comment.

 1public class Main {
 2  // Deletes the smallest value in the BST and returns the root.
 3  static TreeNode deleteMin(TreeNode node) {
 4    // YOUR CODE:
 5    // 1. If node is null (an empty tree), return null.
 6    // 2. If node has no left child, node holds the smallest
 7    //    value. Return node.right (it moves up, or it is null).
 8    // 3. Otherwise the smallest value is in the left subtree:
 9    //    delete it there, and save the answer in node.left.
10
11    return node;
12  }
13
14  // Given: insertRec and inOrder from the Recursion lesson.
15  static TreeNode insertRec(TreeNode node, int value) {
16    if (node == null) {
17      return new TreeNode(value);
18    }
19    if (value < node.data) {
20      node.left = insertRec(node.left, value);
21    } else if (value > node.data) {
22      node.right = insertRec(node.right, value);
23    }
24    return node;
25  }
26
27  static void inOrder(TreeNode node) {
28    if (node == null) { return; }
29    inOrder(node.left);
30    System.out.print(node.data + " ");
31    inOrder(node.right);
32  }
33
34  public static void main(String[] args) {
35    int[] values = {40, 20, 60, 10, 30, 50, 70, 15};
36    TreeNode root = null;
37    for (int i = 0; i < values.length; i++) {
38      root = insertRec(root, values[i]);
39    }
40    root = deleteMin(root);    // deletes 10 (it has a right child, 15)
41    inOrder(root);             // expected: 15 20 30 40 50 60 70
42    System.out.println();
43    System.out.println(root.left.left.data);   // expected: 15
44
45    root = deleteMin(root);    // deletes 15 (a leaf)
46    inOrder(root);             // expected: 20 30 40 50 60 70
47    System.out.println();
48
49    TreeNode small = null;
50    small = insertRec(small, 50);
51    small = insertRec(small, 70);
52    small = insertRec(small, 60);
53    small = deleteMin(small);  // deletes 50, the root
54    System.out.println(small.data);            // expected: 70
55    System.out.println(deleteMin(null) == null); // expected: true
56  }
57}
58
59class TreeNode {
60  int data;
61  TreeNode left;
62  TreeNode right;
63
64  TreeNode(int value) {
65    data = value;
66    left = null;
67    right = null;
68  }
69}

▶ This program runs as is. Try it in the Programiz online compiler: tap Copy, paste it there, and press Run.

Show one possible answer

 1static TreeNode deleteMin(TreeNode node) {
 2  if (node == null) {
 3    return null;
 4  }
 5  if (node.left == null) {
 6    return node.right;
 7  }
 8  node.left = deleteMin(node.left);
 9
10  return node;
11}

Output, one per line: 15 20 30 40 50 60 70, 15, 20 30 40 50 60 70, 70, true.

Which case? The smallest node has no left child, because a left child would be even smaller. So it is case 1 (a leaf) or case 2 (one child, on the right). It is never case 3, so deleteMin never needs a next value. One line covers both cases: return node.right;. For a leaf, node.right is null (case 1). Otherwise the right child moves up (case 2 ).

The tests: first, 10 has a right child, 15. The call for 10 returns 15, and the call for 20 saves it, so 20's left is now 15. Next, 15 is a leaf, so its call returns null, and 20's left becomes empty. In the small tree, 50 has no left child, so the very first call returns 70, and main saves it: 70 is the new root. That is why main writes small = deleteMin(small);.

A common mistake is writing deleteMin(node.left); without node.left = in front. The call for 10 returns 15, but no one saves it, so 10 stays in the tree, and the first line prints 10 15 20 30 40 50 60 70. The small-tree test still passes, because there the answer comes from the very first call, and main saves it. So one passing test does not prove the code is right.

Does this look familiar? "Keep going left until there is no left child" is how deleteRec finds the next value in case 3: right once, then left all the way. The next value is just the smallest value in the right subtree.

Part 9 · Check yourself

Self-check

Not graded. Tap an answer to see if you got it, and read why.

You delete a node with no children. What happens?
You delete a node with one child. What happens?
Starting BST: what is the next value (in-order successor) of 40?
To delete a node with two children, we:
Why is removing the next value always easy?
Deleting 20 (case 3): lines 23–24 make one more call. What is value in that new call?
Someone deletes 40 by copying its right child, 60, into its spot. What goes wrong?
Why must we write root = deleteRec(root, value);?

Score: 0 / 8

Key takeaways

Find the node first, like search.
Case 1, a leaf: remove it. Case 2, one child: the child moves up.
Case 3, two children: copy in the next value, then remove the old one (case 1 or 2).
Next value (for a node with two children): right once, then left as far as you can.
Always write root = deleteRec(root, value);

You've finished the trees unit. You can now insert, traverse, and delete in a BST, by hand and in Java. Next: AVL trees, which keep a BST from becoming a chain.

References

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 4th ed. MIT Press, 2022, Chapter 12 (Binary search trees).
GeeksforGeeks, "Deletion in Binary Search Tree." geeksforgeeks.org
Programiz, "Binary Search Tree (BST)." programiz.com/dsa/binary-search-tree

Why deleting is harder

What you already know

Why not just remove it?

The three cases

Delete a leaf

Delete a node with one child

Like deleting from a linked list

What if 45 has children?

Delete a node with two children

Which value fits in 20's spot?

Finding the next value in the tree

Why the rule works

Delete 20, step by step

Two notes on case 3

Quick check

All three cases in the lab

deleteRec in Java

A first look at the whole method

The two inputs: node and value

Finding the node (lines 3–10)

Cases 1 and 2 in code: delete 50

Case 3 in code: delete 20

When the next value has a child

Why root = matters

Special situations

Three common mistakes

Try it yourself

Self-check

`deleteRec` in Java

The two inputs: `node` and `value`

Why `root =` matters