BST Deletion

Deleting from a BST

Deletion is the trickiest BST operation. There are three cases:

Case 1: Leaf Node (no children)

Simply remove the node by returning NULL to the parent.

Delete 4:       5            5
               / \    →     / \
              3   7        3   7
             / \          /
            1   4        1

Case 2: One Child

Replace the node with its only child.

Delete 3:       5            5
               / \    →     / \
              3   7        1   7
             /
            1

Case 3: Two Children

Find the in-order successor (smallest node in the right subtree), copy its value into the node being deleted, then recursively delete the successor.

Delete 5:       5            6
               / \    →     / \
              3   7        3   7
             / \ /        / \   \
            1  4 6       1   4   8
                  \
                   8

The in-order successor of 5 is 6 (leftmost node in right subtree).

Finding the Minimum

A helper to find the minimum value in a subtree (used to locate the in-order successor):

int bst_min(struct Node *root) {
    while (root->left != NULL)
        root = root->left;
    return root->val;
}

Your Task

Implement struct Node *bst_delete(struct Node *root, int val) that deletes val from the BST and returns the new root.