BST deletion: leaf, one child, two children (inorder successor or predecessor)

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Where does a newly inserted BST key end up? from Lesson 4.5.2
• What does a recursive height function return for a leaf? from Lesson 4.4
• To delete a node from a singly linked list, which other node must you reach? from Lesson 3.4.1

1 · The Hook

🎣

A manager leaves a company. If she had no team, nothing changes. If she had one team, that team now reports to her boss. If she had two teams, someone must step into her chair — and to keep everyone’s seniority order intact, it must be the person whose rank comes right after (or right before) hers.

2 · Predict First

🤔

In the BST 50, 30, 70, 20, 40, 60, 80, 65, the root 50 is deleted using the inorder successor. Which key becomes the new root? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

60: the smallest key in 50’s right subtree. It moves up to the root, and 60’s own right child 65 takes 60’s old place.

Case 1: a leaf

Remove it; its parent’s pointer becomes NULL.

Case 2: one child

Replace the node by its only child (the child’s whole subtree moves up one level). The ordering is preserved because that subtree was on the correct side of the parent.

Case 3: two children

Replace the node’s key by its inorder successor (the minimum of the right subtree) — or its inorder predecessor (the maximum of the left subtree) — and then delete that successor (or predecessor) from its subtree. The successor has no left child, so its own deletion is case 1 or 2.

struct tnode *del(struct tnode *t, int key)
{
    struct tnode *s;
    if (t == NULL) return NULL;
    if (key < t->data)      t->left = del(t->left, key);
    else if (key > t->data) t->right = del(t->right, key);
    else {
        if (t->left == NULL)  { s = t->right; free(t); return s; }   /* 0 or 1 child */
        if (t->right == NULL) { s = t->left;  free(t); return s; }
        s = t->right;                       /* two children: inorder successor */
        while (s->left) s = s->left;
        t->data = s->data;
        t->right = del(t->right, s->data);
    }
    return t;
}

int main(void)
{
    int a[] = {50, 30, 70, 20, 40, 60, 80, 65}, i;
    struct tnode *root = NULL;
    for (i = 0; i < 8; i++) root = insert(root, a[i]);
    root = del(root, 20);  pre(root); printf("\n");    /* leaf */
    root = del(root, 60);  pre(root); printf("\n");    /* one child */
    root = del(root, 50);  pre(root); printf("\n");    /* two children */
    return 0;
}

Output

50 30 40 70 60 65 80 
50 30 40 70 65 80 
65 30 40 70 80

The program deletes 20 (leaf), 60 (one child: 65 moves up), then 50 (two children: successor 65 replaces it).

Successor or predecessor?

Both keep the BST valid; they give different trees. GATE questions say which one to use. Deleting 50 from the original tree: successor → preorder 60 30 20 40 70 65 80; predecessor → preorder 40 30 20 70 60 65 80. Deletion costs O(h).

4 · Visual

Delete 50 with the inorder successor (60 moves up; 65 takes 60’s place).

Delete 50 with the inorder predecessor (40 moves up).

Original:                     after delete(50) using successor:
            50
        /         \
    30                  70
  /   \             /     \
20      40      60          80
                  \
                    65

            60
        /       \
    30              70
  /   \           /   \
20      40      65      80

Case 3 replaces the key, then deletes the successor (a node with at most one child).

5 · Worked Examples

Example 1 Easy

From the original BST, delete 80. Which case is it, and what changes?

Solution

80 is a leaf (case 1): 70’s right pointer becomes NULL.

Example 2 Medium

From the original BST, delete 60. Which case, and what is the preorder afterwards?

Solution

60 has one child (65): case 2. 65 takes its place as 70’s left child. Preorder: 50 30 20 40 70 65 80.

Example 3 GATE

From the original BST, delete 30 using the inorder successor. What replaces 30, and what is the preorder?

Solution

30 has two children (20, 40); its successor is 40 (minimum of {40}). Preorder: 50 40 20 70 60 65 80.

6 · GATE Traps

⚠️

• Two-children deletion moves a key, not a whole subtree; the successor’s own node is then removed.
• The inorder successor has no left child; the predecessor has no right child.
• Successor and predecessor give different trees: use the one the question names.
• Deleting the root may change the root key; the node itself may stay in place.
• Deletion is O(h).

8 · Memory Hook

🧠

“No kids: leave. One kid: the kid moves up. Two kids: the next-in-line sits in the chair.”

9 · Connect the Dots

Lessons 4.5.1–4.5.3 covered search, insertion and deletion. GATE combines them into short puzzles: rebuild a BST from one traversal, count BSTs, check search paths, count insertion orders. Next lesson answers: what are the fastest methods for these recurring BST questions?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markCases

Deleting a BST node with exactly one child:

• (A) replaces it with the inorder successor
• (B) is not allowed
• (C) deletes its whole subtree
• (D) replaces it with its child

Q2MCQ2 marksOutput

What does this print? (three lines)

struct tnode *del(struct tnode *t, int key)
{
    struct tnode *s;
    if (t == NULL) return NULL;
    if (key < t->data)      t->left = del(t->left, key);
    else if (key > t->data) t->right = del(t->right, key);
    else {
        if (t->left == NULL)  { s = t->right; free(t); return s; }   /* 0 or 1 child */
        if (t->right == NULL) { s = t->left;  free(t); return s; }
        s = t->right;                       /* two children: inorder successor */
        while (s->left) s = s->left;
        t->data = s->data;
        t->right = del(t->right, s->data);
    }
    return t;
}

int main(void)
{
    int a[] = {50, 30, 70, 20, 40, 60, 80, 65}, i;
    struct tnode *root = NULL;
    for (i = 0; i < 8; i++) root = insert(root, a[i]);
    root = del(root, 20);  pre(root); printf("\n");    /* leaf */
    root = del(root, 60);  pre(root); printf("\n");    /* one child */
    root = del(root, 50);  pre(root); printf("\n");    /* two children */
    return 0;
}

• (A) as shown in the lesson
• (B) only the last line
• (C) the same line three times
• (D) the inorder of each tree

Q3MCQ2 marksSuccessor

Deleting 50 from the BST of this lesson using the inorder predecessor gives the preorder:

• (A) 40 30 20 70 60 65 80
• (B) 60 30 20 40 70 65 80
• (C) 40 20 30 70 60 65 80
• (D) 30 20 40 70 60 65 80

Q4NAT1 markSuccessor

In the BST built from 50 30 70 20 40 60 80 65, what is the inorder successor of 50?

Numerical answer: ________

Q5MSQ2 marksFacts

Which are true?

• (A) Deleting a leaf never changes any other node’s key.
• (B) Case 3 deletion can be done with either the successor or the predecessor.
• (C) The inorder successor of a node with two children has no left child.
• (D) BST deletion always reduces the height by one.

11 · Rule Card

• Leaf: remove. One child: splice the child up.
• Two children: copy the inorder successor (min of right subtree) or predecessor (max of left), then delete that node (0 or 1 child).
• Successor and predecessor give different valid BSTs.
• O(h).

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

BST deletiondeletion case: leafdeletion case: one childdeletion case: two childreninorder successor replacementinorder predecessor replacement

13 · Answer Vault