Binary search tree - C

bst.c

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


#ifndef _BST_H
#define _BST_H

#define END             0
#define INSERT          1
#define PRINT_INORDER       2
#define PRINT_PREORDER      3
#define PRINT_POSTORDER     4
#define HEIGHT          5
#define SEARCH          6
#define REMOVE          7
#define MAX         8
#define MIN         9
#define PRINT_ASCII         10

typedef struct bst_t {
    int value;
    struct bst_t* left;
    struct bst_t* right;
} bst_t;

bst_t* bst_insert(bst_t*, int);
bst_t* bst_remove(bst_t*, int);
void bst_free(bst_t*);
void bst_print_inorder(bst_t*);
void bst_print_preorder(bst_t*);
void bst_print_postorder(bst_t*);
bst_t*  bst_search(bst_t*, int);
bst_t*  bst_min(bst_t*);
bst_t*  bst_max(bst_t*);
int bst_height(bst_t*);


#endif /* _BST_H */

bst_t*
bst_insert(bst_t* pbst, int new)
{
    if (pbst == NULL) {
        pbst = malloc(sizeof(struct bst_t));
        if (pbst == NULL) {
            perror("bst_insert: malloc");
            exit(EXIT_FAILURE);
        }
        pbst->value =  new;
        pbst->left = NULL;
        pbst->right = NULL;
    }
    else if (new < pbst->value)
        pbst->left = bst_insert(pbst->left, new);
    else if (new > pbst->value)
        pbst->right = bst_insert(pbst->right, new);

    return pbst;
}

bst_t*
bst_remove(bst_t* pbst, int del)
{
    bst_t *tmp;
    if (pbst == NULL)
        return pbst;
    else if (del < pbst->value)
        pbst->left = bst_remove(pbst->left,del);
    else if (del > pbst->value)
        pbst->right = bst_remove(pbst->left,del);
    /*two children*/
    else if (pbst->left != NULL && pbst->right != NULL) 
    {
        tmp = bst_min(pbst->right);
        pbst->value = tmp->value;
        pbst->right = bst_remove(pbst->right,pbst->value);
    }
    /*zero or one child*/
    else{
        tmp = pbst;
        if(pbst->left == NULL)
            pbst=pbst->right;
        else if(pbst->right == NULL)
            pbst=pbst->left;
        free(tmp);
    }
    return pbst;

}

void 
bst_free(bst_t* pbst)
{
	if (pbst != NULL) {
		bst_free(pbst->left);
		bst_free(pbst->right);
		free(pbst);
	}
}

void 
bst_print_inorder(bst_t* pbst)
{
    if(pbst) {
        bst_print_inorder(pbst->left);
        fprintf(stdout,"%d\n",pbst->value);
        bst_print_inorder(pbst->right);
    }
}

void 
bst_print_preorder(bst_t* pbst)
{
    if (pbst)
    {
        fprintf(stderr, "%d\n", pbst->value);
        bst_print_preorder(pbst->left);
        bst_print_preorder(pbst->right);
    }
}

void 
bst_print_postorder(bst_t* pbst)
{
    if (pbst)
    {
        bst_print_postorder(pbst->left);
        bst_print_postorder(pbst->right);
        fprintf(stderr, "%d\n", pbst->value);
    }
}

bst_t* 
bst_search(bst_t* pbst, int qry)
{
    if(pbst == NULL)
        fprintf(stderr, "Have not found!\n");
    if(qry < pbst->value)
        pbst->left = bst_search(pbst->left,qry);
    else if(qry > pbst->value)
        pbst->right = bst_search(pbst->right,qry);
    
    return pbst;

}

bst_t* 
bst_min(bst_t* pbst)
{
    if(pbst == NULL)
        return NULL;
    if (pbst->left == NULL)
        return pbst;
    else
        return bst_min(pbst->left);
}

bst_t* 
bst_max(bst_t* pbst)
{
	if(pbst == NULL)
        return NULL;
    if (pbst->right == NULL)
        return pbst;
    else
        return bst_max(pbst->right);
}

int 
bst_height(bst_t* pbst)
{
    int tmp1,tmp2;
    if (pbst)
    {
        tmp1 = bst_height(pbst->left);
        tmp2 = bst_height(pbst->right);
        if (tmp1>tmp2)
            return tmp1+1;
        else
            return tmp2+1;
    }
}