Concerning Binary Search Trees(B

The range query function's skipped because I haven't decided in what form to return the results.

/**
* Here I present a full impl of a binary search tree ADT in C.
*/
typedef struct BSTNodeStruct {
    struct BSTNodeStruct *left;
    struct BSTNodeStruct *right;
    int key;
    int value;
    int count;
}*BSTNode;

typedef BSTNode BSTree;

BSTree BSTreeCreate(int key, int val) {
    BSTree bst = (BSTree)malloc(sizeof(*bst));
    bst->left = bst->right = NULL;
    bst->value = val;
    bst->key = key;
    bst->count = 1;
    return bst;
}

void BSTNodeRelease(BSTNode node) { if (node != NULL) free(node); }

void BSTreeRelease(BSTree bst) { 
    if (bst == NULL) return;
    if (bst->left != NULL) BSTreeRelease(bst->left);
    if (bst->right != NULL) BSTreeRelease(bst->right);
    BSTNodeRelease(bst); 
}

int BSTreeCount(BSTree bst) { return bst == NULL ? 0 : bst->count; }

int BSTreeGet(BSTree bst, int key) {
    if (bst == NULL) return INT_MIN;
    int com = key - bst->key;
    if (com < 0) {
        return BSTreeGet(bst->left, key);
    } else if (com > 0) {
        return BSTreeGet(bst->right, key);
    } else {
        return bst->value;
    }
}

BSTree BSTreeSet(BSTree bst, int key, int val) {
    if (bst == NULL) return BSTreeCreate(key, val);
    int com = key - bst->key;
    if (com < 0) {
        bst->left = BSTreeSet(bst->left, key, val);
    } else if (com > 0) {
        bst->right = BSTreeSet(bst->right, key, val);
    } else {
        bst->value = val;
    }
    bst->count = BSTreeCount(bst->left) + BSTreeCount(bst->right) + 1;
    return bst;
}

BSTNode BSTreeMin(BSTree bst) {
    if (bst == NULL) return NULL;
    if (bst->left == NULL) {
        return bst;
    } else {
        return BSTreeMin(bst->left); 
    }
}

BSTNode BSTreeMax(BSTree bst) {
    if (bst == NULL) return NULL;
    if (bst->right == NULL) {
        return bst;
    } else {
        return BSTreeMax(bst->right); 
    }
}

int BSTreeFloor(BSTree bst, int key) {
    if (bst == NULL) return INT_MIN;
    int com = key - bst->key;
    if (com < 0) {
        return BSTreeFloor(bst->left, key);
    } else if (com > 0) {
        int floor = BSTreeFloor(bst->right, key);
        return floor == INT_MIN ? bst->key : floor;
    } else {
        return bst->key;
    }
}

int BSTreeCeiling(BSTree bst, int key) {
    if (bst == NULL) return INT_MIN;
    int com = key - bst->key;
    if (com < 0) {
        int ceiling = BSTreeCeiling(bst->left, key);
        return ceiling == INT_MIN ? bst->key : ceiling;
    } else if (com > 0) {
        return BSTreeCeiling(bst->right, key);
    } else {
        return bst->key;
    }
    return 0;
}

/**
 * The definitions of rank&selection are somewhat confusing...
*/
int BSTreeSelect(BSTree bst, int rank) {
    if (bst == NULL) return INT_MIN;
    int count = BSTreeCount(bst->left);
    if (rank < count) {
        return BSTreeSelect(bst->left, rank);
    } else if (rank > count) {
        return BSTreeSelect(bst->right, rank - 1 - count);
    } else {
        return bst->key;
    }
}

int BSTreeRank(BSTree bst, int key) {
    if (bst == NULL) return 0;
    int com = key - bst->key;
    if (com < 0) {
        return BSTreeRank(bst->left, key);
    } else if (com > 0) {
        return BSTreeRank(bst->right, key) + 1 + (bst->left != NULL ? bst->left->count : 0);
    } else {
        return bst->left == NULL ? 0 : bst->left->count;
    }
}

BSTNode BSTreeDeleteMin(BSTree bst) {
    if (bst == NULL) return NULL;
    if (bst->left == NULL) {
        if (bst->right == NULL) {//last node
            free(bst);
            return NULL;
        } else {
            return bst->right;
        }
    } else {
        BSTNode x = bst->left;
        bst->left = BSTreeDeleteMin(bst->left);
        bst->count = BSTreeCount(bst->left) + BSTreeCount(bst->right) + 1;
        if (x != bst->left) { BSTNodeRelease(x); }
        return bst;
    }
}

BSTNode BSTreeDeleteMax(BSTree bst) {
    if (bst == NULL) return NULL;
    if (bst->right == NULL) {
        if (bst->left == NULL) {//last node
            free(bst);
            return NULL;
        } else {
            return bst->left;
        }
    } else {
        BSTNode x = bst->right;
        bst->right = BSTreeDeleteMax(bst->right);
        bst->count = BSTreeCount(bst->left) + BSTreeCount(bst->right) + 1;
        if (x != bst->right) { BSTNodeRelease(x); }
        return bst;
    }
}

/**
 * The deletion process work by moving the contents of the min node in the right sub bst and delete this min node.
*/
BSTNode BSTreeDelete(BSTree bst, int key) {
    if (bst == NULL) return NULL;
    if (key < bst->key) {
        bst->left = BSTreeDelete(bst->left, key);
    } else if (key > bst->key) {
        bst->right = BSTreeDelete(bst->right, key);
    } else {
        if (bst->left == NULL) {
            BSTNodeRelease(bst);
            return bst->right;
        }
        if (bst->right == NULL) {
            BSTNodeRelease(bst);
            return bst->left;
        }
        //The order of the following instructions can not be changed.
        BSTNode t = bst;
        bst = BSTreeMin(bst->right);
        bst->right = BSTreeDeleteMin(t->right);
        bst->left = t->left;
    }
    bst->count = BSTreeCount(bst->left) + BSTreeCount(bst->right) + 1;
    return bst;
}

#define L -1
#define R 1
#define P 0
void BSTreePrintLevel(BSTree bst, int level, int k) {
    if (bst == NULL) return;
    int i = level;
    while (i-- > 0) { printf("-"); }
    printf("{%s %i: %i; %i %s}\n", k == L ? "'" : "", bst->key, bst->value, bst->count, k == R ? "'" : "");
    if (bst->left != NULL) { BSTreePrintLevel(bst->left, level + 1, L); }
    if (bst->right != NULL) { BSTreePrintLevel(bst->right, level + 1, R); }
}

void BSTreePrint(BSTree bst) {
    if (bst == NULL) return;
    BSTreePrintLevel(bst, 0, P);
}