Binary search tree implementation in C

bst.c

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

typedef struct node Node;

struct node {
    int value;
    Node *left;
    Node *right;
};

Node* insert(Node *root, int v) {
    if (root == NULL) {
        root = malloc(sizeof (Node));
        root->value = v;
        root->left = NULL;
        root->right = NULL;
    } else if (v < root->value) {
        root->left = insert(root->left, v);
    } else {
        root->right = insert(root->right, v);
    }

    return root;
}

void traverse(Node *root) {
    if (root == NULL) {
        return;
    }

    traverse(root->left);
    traverse(root->right);
}

int main(int argc, char** argv) {
    Node *root = NULL;
    const int SIZE = 2000000;
    int *a = malloc(sizeof (int)*SIZE);
    clock_t start, end;

    printf("Generating random array with %d values...\n", SIZE);

    start = clock();

    for (int i = 0; i < SIZE; i++) {
        a[i] = rand() % 10000;
    }

    end = clock();

    printf("Done. Took %f seconds\n\n", (double) (end - start) / CLOCKS_PER_SEC);
    printf("Filling the tree with %d nodes...\n", SIZE);

    start = clock();

    for (int i = 0; i < SIZE; i++) {
        root = insert(root, a[i]);
    }

    end = clock();
    free(a);

    printf("Done. Took %f seconds\n\n", (double) (end - start) / CLOCKS_PER_SEC);
    printf("Traversing all %d nodes in tree...\n", SIZE);

    start = clock();

    traverse(root);

    end = clock();
    free(root);

    printf("Done. Took %f seconds\n\n", (double) (end - start) / CLOCKS_PER_SEC);

    return (EXIT_SUCCESS);
}

Cool

How can we define a search function for this example?

legend

so beautiful code!

I'm wondering that your free() used in line 74 may not enough. You just freed the memory pointered by root. But the memory pointered by the artribute Node* type left and Node * type right is still not freed, Which will lead to memory leak.

`void freeForBtree(Node * root){
if(root==NULL)
{
return;
}
free(root);
else{
freeForBtree(root->left);
freeForBtree(root->right);
}
}'
this is the free routine I have write for your program, I hope it's not wrong,hhh