bst

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


#define N 25

typedef struct _bst
{
    struct _bst *left, *right;
    int value;
}BST;

void bst_inorder(BST* root)
{
    if(root != NULL)
    {
        bst_inorder(root->left);
        printf("%d ",root->value);
        bst_inorder(root->right);
    }
}

void bst_add(BST* root, int num)
{
    if(num < root->value)
    {
        if(root->left == NULL)
        {
            root->left = calloc(1,sizeof(BST));
            root->left->value = num;
        }else{
            bst_add(root->left,num);
        }
    }else if(num > root->value)
    {
        if(root->right == NULL)
        {
            root->right = calloc(1,sizeof(BST));
            root->right->value = num;
        }else{
            bst_add(root->right,num);
        }
    }
}

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

int bst_greater(BST* root, int num)
{
    if(root != NULL)
    {
        if(num < root->value)
        {
            return bst_greater(root->left,num) + bst_greater(root->right,num) + 1;
        }else{
            return bst_greater(root->right,num);
        }
    }
    return 0;
}

int bst_smaller(BST* root, int num)
{
    if(root != NULL)
    {
        int retval = bst_smaller(root->left,num) + bst_smaller(root->right,num);
        if(root->value < num)
            ++retval;
        return retval;
    }
    return 0;
}

int main()
{
    int values_to_add[N], i, a = 50, b = 7;

    srand(time(NULL));
    printf("Array contents: ");
    for(i=0;i<N;i++)
        printf("%d ",values_to_add[i] = rand()%100);

    printf("\n");

    BST* root = calloc(1,sizeof(BST));
    root->value = values_to_add[0];

    for(i=1;i<N;i++)
        bst_add(root,values_to_add[i]);

    printf("Binary tree: ");
    bst_inorder(root);
    printf("\nNumbers in bst tree greater than %d: %d\n",a,bst_greater(root,a));
    printf("\nNumbers in bst tree smaller than %d: %d\n",b,bst_smaller(root,b));

    bst_free(root);


    return 0;
}