QUESTION 11

What are the three BST deletion cases?

2 marks

Answer

The target has zero children, one child or two children. The two-child case uses a suitable predecessor or successor replacement.

Explain all BST deletion cases with an algorithm.

5 marks

Answer in brief

BST deletion must remove the target while preserving every subtree’s ordering relationship.

Algorithm

Search recursively or iteratively for the key. A missing key leaves the tree unchanged.
For a leaf, free it and replace its parent link with NULL.
For one child, replace the target link with its child, then free the target.
For two children, find the minimum node in the right subtree, copy its key or full associated record as appropriate, and delete that successor from the right subtree.

Why the successor works

The right-subtree minimum is greater than every key in the left subtree and no larger than the remaining right-subtree keys. It has no left child, so deleting its old node reduces to a simpler case. Do not copy a whole node object including its link pointers as though that were only a key replacement.

Example

The demonstration builds 50, 30, 70, 20, 40, 60, 80. It deletes 20 as a leaf, 30 as a one-child node and 50 as a two-child root. The final inorder sequence is 40, 60, 70, 80.

Boundary cases

Deleting the root can change the root pointer. Removing the only node makes the tree empty. Free exactly the removed node and keep no usable alias to it. A missing-key deletion is a normal unsuccessful operation.

Complexity

Search and successor location follow paths bounded by tree height, giving O(h) time. Worst case is O(n), not unconditionally logarithmic. Recursive deletion uses O(h) call space. Destroy all remaining owned nodes when finished.

Diagram or flowchart

CodeBhavya illustration of bst delete — Explain all BST deletion cases with an algorithm. · Download diagram

Complete C example

main.c

Download main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <stdlib.h>
struct Node { int key; struct Node *left, *right; };
struct Node *insert(struct Node *root, int key, int *ok)
{
    if (root == NULL) {
        struct Node *node = malloc(sizeof *node);
        if (node == NULL) { *ok = 0; return NULL; }
        node->key = key; node->left = node->right = NULL; return node;
    }
    if (key < root->key) { root->left = insert(root->left, key, ok); }
    else if (key > root->key) { root->right = insert(root->right, key, ok); }
    return root;
}
const struct Node *search(const struct Node *root, int key)
{
    while (root != NULL && root->key != key) { root = key < root->key ? root->left : root->right; }
    return root;
}
struct Node *remove_key(struct Node *root, int key)
{
    if (root == NULL) { return NULL; }
    if (key < root->key) { root->left = remove_key(root->left, key); }
    else if (key > root->key) { root->right = remove_key(root->right, key); }
    else {
        if (root->left == NULL) { struct Node *next = root->right; free(root); return next; }
        if (root->right == NULL) { struct Node *next = root->left; free(root); return next; }
        struct Node *successor = root->right;
        while (successor->left != NULL) { successor = successor->left; }
        root->key = successor->key;
        root->right = remove_key(root->right, successor->key);
    }
    return root;
}
void inorder(const struct Node *root)
{
    if (root != NULL) { inorder(root->left); printf("%d ", root->key); inorder(root->right); }
}
void destroy(struct Node *root)
{
    if (root != NULL) { destroy(root->left); destroy(root->right); free(root); }
}

int main(void)
{
    struct Node *root = NULL; int ok = 1;
    int keys[7] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; ++i) {
        root = insert(root, keys[i], &ok);
        if (!ok) { destroy(root); puts("Allocation failed"); return 1; }
    }
    printf("Search 40: %s\n", search(root, 40) != NULL ? "Found" : "Not found");
    root = remove_key(root, 20); root = remove_key(root, 30); root = remove_key(root, 50);
    inorder(root); putchar('\n'); destroy(root); root = NULL;
    return 0;
}

Sample input and output

The example uses values in the code.

Output

Search 40: Found
40 60 70 80