Binary Search Tree

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

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

Tree *insert(Tree *t, int key) {
    if (!t) {
        t = malloc(sizeof *t);
        if (!t) exit(1);
        t->key = key; t->left = t->right = NULL;
    } else if (key < t->key) t->left = insert(t->left, key);
    else if (key > t->key)   t->right = insert(t->right, key);
    return t;                                  /* duplicates ignored */
}

const Tree *search(const Tree *t, int key) {
    while (t && t->key != key) t = key < t->key ? t->left : t->right;
    return t;
}

Tree *delete(Tree *t, int key) {
    if (!t) return NULL;
    if (key < t->key) t->left = delete(t->left, key);
    else if (key > t->key) t->right = delete(t->right, key);
    else if (!t->left || !t->right) {          /* 0 or 1 child */
        Tree *child = t->left ? t->left : t->right;
        free(t);
        return child;
    } else {                                   /* 2 children: copy in-order successor */
        Tree *s = t->right;
        while (s->left) s = s->left;
        t->key = s->key;
        t->right = delete(t->right, s->key);
    }
    return t;
}

void inorder(const Tree *t)  { if (t) { inorder(t->left); printf("%d ", t->key); inorder(t->right); } }
void preorder(const Tree *t) { if (t) { printf("%d ", t->key); preorder(t->left); preorder(t->right); } }
int height(const Tree *t) {
    if (!t) return 0;
    int l = height(t->left), r = height(t->right);
    return 1 + (l > r ? l : r);
}
void destroy(Tree *t) { if (t) { destroy(t->left); destroy(t->right); free(t); } }  /* postorder */

int main(void) {
    Tree *root = NULL;
    int keys[] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; i++) root = insert(root, keys[i]);

    printf("inorder:  "); inorder(root);  printf("\n");
    printf("preorder: "); preorder(root); printf("\n");
    printf("height %d, has 60? %s, has 65? %s\n", height(root),
           search(root, 60) ? "yes" : "no", search(root, 65) ? "yes" : "no");

    root = delete(root, 50);                   /* root with two children */
    printf("after deleting 50: "); inorder(root); printf("(root %d)\n", root->key);
    destroy(root);
    return 0;
}

inorder:  20 30 40 50 60 70 80
preorder: 50 30 20 40 70 60 80
height 3, has 60? yes, has 65? no
after deleting 50: 20 30 40 60 70 80 (root 60)