Delete from a search tree – Data Structures Practice

Remove keys from a binary search tree so that it stays a correct search tree.

What to build

A delete_key function that handles a leaf, a node with one child and a node with two children.

Requirements

Build the tree by inserting the keys in the order given.
Delete each of the given keys in turn, ignoring a key that is not in the tree.
For a node with two children, replace its key with its inorder successor, the smallest key in its right subtree.
Print the keys left in the tree in preorder, or empty.

Input

The first line has n, and the second has n different keys. The third line has q, and the fourth has the q keys to delete.

Output

The remaining keys in preorder on one line, separated by spaces, or empty.

Constraints

1 ≤ n ≤ 100 and 1 ≤ q ≤ 100.

Example

Input:

7
50 30 70 20 40 60 80
3
20 30 50

Output:

60 40 70 80

Why it works

The inorder successor is larger than everything in the left subtree and smaller than everything else in the right subtree, so it can take the deleted key's place without breaking the search order. It has no left child, so removing it is one of the easy cases.

Examples

Example 1 · Input

7
50 30 70 20 40 60 80
3
20 30 50

Expected output

60 40 70 80

Example 2 · Input

Expected output

empty

Hints

Hint 1

First find the node, going left or right and storing the result of the recursive call.

Hint 2

With no child or one child, free the node and return its child, which may be NULL.

Hint 3

With two children, copy in the smallest key of the right subtree, then delete that key from the right subtree.

Solution

Show one correct solution (try it yourself first)

#include <stdio.h>
#include <stdlib.h>

typedef struct tree {
    int key;
    struct tree *left, *right;
} Tree;

Tree *insert(Tree *t, int key) {
    if (t == NULL) {
        Tree *n = malloc(sizeof(Tree));
        n->key = key;
        n->left = NULL;
        n->right = NULL;
        return n;
    }
    if (key < t->key) t->left = insert(t->left, key);
    else if (key > t->key) t->right = insert(t->right, key);
    return t;
}

Tree *delete_key(Tree *t, int key) {
    if (t == NULL) return NULL;
    if (key < t->key) {
        t->left = delete_key(t->left, key);
    } else if (key > t->key) {
        t->right = delete_key(t->right, key);
    } else if (t->left != NULL && t->right != NULL) {
        Tree *s = t->right;
        while (s->left != NULL) s = s->left;
        t->key = s->key;
        t->right = delete_key(t->right, s->key);
    } else {
        Tree *child = t->left != NULL ? t->left : t->right;
        free(t);
        return child;
    }
    return t;
}

void preorder(Tree *t, int *first) {
    if (t == NULL) return;
    if (!*first) printf(" ");
    *first = 0;
    printf("%d", t->key);
    preorder(t->left, first);
    preorder(t->right, first);
}

void free_tree(Tree *t) {
    if (t == NULL) return;
    free_tree(t->left);
    free_tree(t->right);
    free(t);
}

int main(void) {
    int n, q;
    scanf("%d", &n);
    Tree *root = NULL;
    for (int i = 0; i < n; i++) {
        int key;
        scanf("%d", &key);
        root = insert(root, key);
    }
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        int key;
        scanf("%d", &key);
        root = delete_key(root, key);
    }
    int first = 1;
    if (root == NULL) printf("empty");
    preorder(root, &first);
    printf("\n");
    free_tree(root);
    return 0;
}

Lesson: Binary search trees →