Unbalanced Binary Search Tree insertion and search with random and sorted values 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 &lt;stdlib.h&gt;
#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;time.h&gt;

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)-&gt;BSTLeft = NULL;
        (*n)-&gt;BSTRight = NULL;
        (*n)-&gt;data = i;
    }
    else if (i &gt; (*n)-&gt;data)
        BSTInsert(i, &amp;((*n)-&gt;BSTRight));
    else
        BSTInsert(i, &amp;((*n)-&gt;BSTLeft));
}

void BSTSearch(int i, node **n) {
    if (*n == NULL)
        printf("\nValue does not exist in tree!");
    else if((*n)-&gt;data == i)
       return ;
    else if(i &gt; (*n)-&gt;data)
        BSTSearch(i, &amp;((*n)-&gt;BSTRight));
    else
        BSTSearch(i, &amp;((*n)-&gt;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 &lt; 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 &lt; SIZE; i++) {
    BSTInsert(a[i], &amp;rootNode);
    }
    end = clock();
    printf("Done. Took %.8f seconds\n\n", (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 &lt; SIZE; i++) {
    BSTSearch(a[i], &amp;rootNode);
    }
    end = clock();
    printf("\nDone. Took %.8f seconds\n", (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&lt;=10000;num++){
    BSTInsert(num, &amp;rootNode);
    }
    end = clock();
    printf("Done. Took %.8f seconds\n\n", (double) (end - start) / CLOCKS_PER_SEC);

// Search in BST with sorted Values

    printf("Searching sorted values in BST...");
    start = clock();
    for (num=1;num&lt;=10000;num++)
    BSTSearch(num, &amp;rootNode);
    end = clock();
    printf("\nDone. Took %.8f seconds\n\n", (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 &lt; 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)-&gt;BSTLeft = NULL;
    (*n)-&gt;BSTRight = NULL;
    (*n)-&gt;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)-&gt;data == i)
   return ;
else if(i &gt; (*n)-&gt;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)-&gt;data)
   return;
else if (i &gt; (*n)-&gt;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)-&gt;BSTLeft = NULL;
    (*n)-&gt;BSTRight = NULL;
    (*n)-&gt;data = i;
} else if (i &gt; (*n)-&gt;data) {
    BSTInsert(i, &amp;((*n)-&gt;BSTRight));
} else {
    BSTInsert(i, &amp;((*n)-&gt;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-&gt;BSTLeft = NULL;
        node-&gt;BSTRight = NULL;
        node-&gt;data = i;
    } else if (i &gt; node-&gt;data) {
        BSTInsert(i, &amp;node-&gt;BSTRight);
    } else {
        BSTInsert(i, &amp;node-&gt;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-&gt;data) {
       return &amp;n-&gt;data;
    } else if (i &gt; n-&gt;data) {
        return BSTSearch(i, n-&gt;BSTRight);
    } else {
        return BSTSearch(i, n-&gt;BSTLeft);
    }
}


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



The parallel structure of insert and search suggests that we're missing a condition for (i == n-&gt;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-&gt;BSTLeft = NULL;
        node-&gt;BSTRight = NULL;
        node-&gt;data = i;
    } else if (i == node-&gt;data) {
        return;                 /* already exists */
    } else if (i &gt; node-&gt;data) {
        BSTInsert(i, &amp;node-&gt;BSTRight);
    } else {
        BSTInsert(i, &amp;node-&gt;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-&gt;BSTLeft = NULL;
        node-&gt;BSTRight = NULL;
        node-&gt;data = i;
        return true;
    } else if (i == node-&gt;data) {
        return true;            /* already exists */
    } else if (i &gt; node-&gt;data) {
        return BSTInsert(i, &amp;node-&gt;BSTRight);
    } else {
        return BSTInsert(i, &amp;node-&gt;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).