Cfrtjryk

I have created this unbalanced binary search tree in C. Can anyone say this is a true approach or not? I have two scenarios for insertion and search: in the first scenario I am inserting 10000 random values to tree, and in the second scenario I am inserting 10000 sorted values from 1 to 10000.

Am I on the right track?

#include <stdlib.h>

#include <stdio.h>

#include <string.h>

#include <time.h>



struct BSTNode {

    int data;

    struct BSTNode *BSTLeft;

    struct BSTNode *BSTRight;

};



typedef struct BSTNode node;



node *rootNode= NULL;



void BSTInsert(int i, node **n) {

    if (*n == NULL) {

        (*n) = (node*)malloc(sizeof(node));

        (*n)->BSTLeft = NULL;

        (*n)->BSTRight = NULL;

        (*n)->data = i;

    }

    else if (i > (*n)->data)

        BSTInsert(i, &((*n)->BSTRight));

    else

        BSTInsert(i, &((*n)->BSTLeft));

}



void BSTSearch(int i, node **n) {

    if (*n == NULL)

        printf("nValue does not exist in tree!");

    else if((*n)->data == i)

       return ;

    else if(i > (*n)->data)

        BSTSearch(i, &((*n)->BSTRight));

    else

        BSTSearch(i, &((*n)->BSTLeft));

}



void test_scenario1() {    

    node *rootNode = NULL;

    const int SIZE = 10000;

    int *a = malloc(sizeof (int)*SIZE);

    clock_t start, end;

    for (int i = 1; i < SIZE; i++)

    {

        srand(time(NULL));

        a[i] = rand() % 1000;

    }

    printf("Inserting values to BST with %d random nodes...n", SIZE);

    start = clock();

    for (int i = 0; i < SIZE; i++) {

    BSTInsert(a[i], &rootNode);

    }

    end = clock();

    printf("Done. Took %.8f secondsnn", (double) (end - start) / CLOCKS_PER_SEC);



// Search in BST with random Values



    printf("Searching random values in BST...");

    start = clock();

    for (int i = 0; i < SIZE; i++) {

    BSTSearch(a[i], &rootNode);

    }

    end = clock();

    printf("nDone. Took %.8f secondsn", (double) (end - start) / CLOCKS_PER_SEC);

    free(a);

}



void test_scenario2(){

    node *rootNode = NULL;

    const int SIZE = 10000;

    clock_t start, end;

    int num;

    printf("nInserting values to BST with %d sorted nodes...n", SIZE);

    start = clock();

    for (num=1;num<=10000;num++){

    BSTInsert(num, &rootNode);

    }

    end = clock();

    printf("Done. Took %.8f secondsnn", (double) (end - start) / CLOCKS_PER_SEC);



// Search in BST with sorted Values



    printf("Searching sorted values in BST...");

    start = clock();

    for (num=1;num<=10000;num++)

    BSTSearch(num, &rootNode);

    end = clock();

    printf("nDone. Took %.8f secondsnn", (double) (end - start) / CLOCKS_PER_SEC);

}

// Main function for these three scenarios.

int main(int argc, char ** argv)

{

    test_scenario1();

    test_scenario2();

}

The global variable rootNode is never used, and is confusing due to similar local variables, so remove it.

As we're ignoring all command-line arguments, we can use the simpler signature for main():

int main(void)

Prefer to use unsigned types for counting:

const unsigned int SIZE = 10000;

...

for (unsigned int i = 1;  i < SIZE;  ++i)

That addresses most of the compiler warnings I get for this code. The remaining warning is best eliminated with a cast to indicate that we don't care about preserving the correct value in this signed → unsigned conversion:

    srand((unsigned)time(NULL));

Prefer to use the size of the variable than of its type when allocating memory. This makes it easier for reviewers to confirm that the sizes match:

if (!*n) {

    *n = malloc(sizeof **n);

    (*n)->BSTLeft = NULL;

    (*n)->BSTRight = NULL;

    (*n)->data = i;

}

and

int *a = malloc(sizeof *a * SIZE);

Use a memory checker; at the moment, we leak the entire BST:

Inserting values to BST with 10000 random nodes...

==12434== Conditional jump or move depends on uninitialised value(s)

==12434==    at 0x1091FC: BSTInsert (209085.c:24)

==12434==    by 0x109388: test_scenario1 (209085.c:54)

==12434==    by 0x10956F: main (209085.c:96)

==12434== 

Done. Took 3.30890200 seconds



==12434== Conditional jump or move depends on uninitialised value(s)

==12434==    at 0x10926D: BSTSearch (209085.c:33)

==12434==    by 0x10940C: test_scenario1 (209085.c:64)

==12434==    by 0x10956F: main (209085.c:96)

==12434== 

==12434== Conditional jump or move depends on uninitialised value(s)

==12434==    at 0x10927B: BSTSearch (209085.c:35)

==12434==    by 0x10940C: test_scenario1 (209085.c:64)

==12434==    by 0x10956F: main (209085.c:96)

==12434== 

Searching random values in BST...

Done. Took 0.00558500 seconds



Inserting values to BST with 10000 sorted nodes...

Done. Took 3.36596000 seconds



Searching sorted values in BST...

Done. Took 3.96642300 seconds



==12434== 240,000 (24 direct, 239,976 indirect) bytes in 1 blocks are definitely lost in loss record 22 of 23

==12434==    at 0x483577F: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)

==12434==    by 0x1091B9: BSTInsert (209085.c:19)

==12434==    by 0x109388: test_scenario1 (209085.c:54)

==12434==    by 0x10956F: main (209085.c:96)

==12434== 

==12434== 240,000 (24 direct, 239,976 indirect) bytes in 1 blocks are definitely lost in loss record 23 of 23

==12434==    at 0x483577F: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)

==12434==    by 0x1091B9: BSTInsert (209085.c:19)

==12434==    by 0x1094AA: test_scenario2 (209085.c:79)

==12434==    by 0x109579: main (209085.c:97)

==12434== 

Those early reports of using uninitialised values are certainly worth investigating, too.

Try to be consistent where that helps readers. Consider this fragment:

else if((*n)->data == i)

   return ;

else if(i > (*n)->data)

See how it's easier to see the relation between the two tests if we write the operands in the same order:

else if (i == (*n)->data)

   return;

else if (i > (*n)->data)

Use the standard error stream for error messages:

if (*n == NULL)

    fprintf(stderr, "Value does not exist in tree!n");

And prefer to write complete lines to output (especially relevant when it's connected to line-buffered devices, such as terminals and terminal-emulators).

Consider using more braces to enclose conditional commands. It's easier to avoid silly mistakes:

if (*n == NULL) {

    *n = malloc(sizeof **n);

    (*n)->BSTLeft = NULL;

    (*n)->BSTRight = NULL;

    (*n)->data = i;

} else if (i > (*n)->data) {

    BSTInsert(i, &((*n)->BSTRight));

} else {

    BSTInsert(i, &((*n)->BSTLeft));

}

We could make that code a lot clearer by copying *n into a local variable:

void BSTInsert(int i, node **n)

{

    node *node = *n;

    if (!node) {

        *n = node = malloc(sizeof **n);

        node->BSTLeft = NULL;

        node->BSTRight = NULL;

        node->data = i;

    } else if (i > node->data) {

        BSTInsert(i, &node->BSTRight);

    } else {

        BSTInsert(i, &node->BSTLeft);

    }

}

On the other hand, in the search function, we don't need to pass by pointer, and we can use const. We probably ought to return something, too:

const int *BSTSearch(int i, const node *n) {

    if (n == NULL) {

        fprintf(stderr, "Value does not exist in tree!n");

        return NULL;

    } else if (i == n->data) {

       return &n->data;

    } else if (i > n->data) {

        return BSTSearch(i, n->BSTRight);

    } else {

        return BSTSearch(i, n->BSTLeft);

    }

}

Obviously, the call sites would then need to pass rootNode by value, rather than &rootNode pointer.

The parallel structure of insert and search suggests that we're missing a condition for (i == n->data) in the insert; in that block, we should avoid inserting a duplicate node and instead return early:

void BSTInsert(int i, node **n)

{

    node *node = *n;

    if (!node) {

        *n = node = malloc(sizeof **n);

        node->BSTLeft = NULL;

        node->BSTRight = NULL;

        node->data = i;

    } else if (i == node->data) {

        return;                 /* already exists */

    } else if (i > node->data) {

        BSTInsert(i, &node->BSTRight);

    } else {

        BSTInsert(i, &node->BSTLeft);

    }

}

(It might be this change that eliminated the Valgrind warning about uninitialised data - I'm not sure when that disappeared).

We're missing the check that malloc() didn't return a null pointer. That can happen any time we call an allocation function, so we must always test the result before using it. In particular, there's no guarantee that the subsequent use of a null pointer will crash the program, as some authors seem to think.

bool BSTInsert(int i, node **n)

{

    node *node = *n;

    if (!node) {

        *n = node = malloc(sizeof **n);

        if (!node) return false;

        node->BSTLeft = NULL;

        node->BSTRight = NULL;

        node->data = i;

        return true;

    } else if (i == node->data) {

        return true;            /* already exists */

    } else if (i > node->data) {

        return BSTInsert(i, &node->BSTRight);

    } else {

        return BSTInsert(i, &node->BSTLeft);

    }

}

Don't forget that this means that the callers of BSTInsert now need to check that it succeeded!

Lastly (and leastly), this comment is inaccurate:

// Main function for these three scenarios.

Either change the word "three" to "two" or remove the comment (it's stating the obvious, so doesn't add any value).

• Do not cast results of malloc.




• BSTSearch does not modify the tree, so there is no need to use double indirection. BSTSearch(int i, node *n) works well.




• BSTSearch does the search, but does not tell the caller whether the search was successful or not. Return something useful (a matching node e.g.).




• I do not endorse recursion when an iterative solution is readily available.