Delete BST node with one child

Rule: if the node to be deleted has exactly one child, the node is removed and its only child (with the whole subtree below it) takes its place by linking the child directly to the deleted node's parent. The BST property is preserved because the child subtree already lies in the correct range for that position.

Steps

1. Search for the node X (and keep a pointer to its parent P).
2. Let C be the only child of X (left or right).
3. If X is the root, make C the new root.
4. Else if X is the left child of P, set P->left = C; otherwise set P->right = C.
5. Free X.

Example

Delete 18 from the BST (18 has only a left child 13):

Before:                     After:
       20                       20
      /  \                    /  \
    10    47                 10    47
   /  \                    /  \
  4    18   <- delete      4    13
      /                         
    13

Parent 10 now points to 13 instead of 18. In-order traversal before: 4 10 13 18 20 47; after: 4 10 13 20 47, still sorted.

Code

struct node { int info; struct node *left, *right; };

struct node *delete_one_child(struct node *root, int key) {
    struct node *p = NULL, *x = root, *c;
    while (x != NULL && x->info != key) {      /* find x and its parent */
        p = x;
        x = (key < x->info) ? x->left : x->right;
    }
    if (x == NULL) return root;                /* key not found */
    c = (x->left != NULL) ? x->left : x->right; /* the only child */
    if (p == NULL)            root = c;        /* deleting the root */
    else if (p->left == x)    p->left = c;
    else                      p->right = c;
    free(x);
    return root;
}

Time: O(h), where h is the height of the tree.