non-recursive binary search tree without return

btree-norec.c

#include <stdio.h>
#include <stdlib.h>
#include "numbers.h" // https://gist.github.com/911872

struct node {
    int key;
    struct node *l;
    struct node *r;
};

/*
  This exists because I wanted to:
   * make a non-recursive binary search tree
   * not have to use a global structure
   * not have to return the structure after insertion
   * have a headache
*/
/*
  On average, this is 10% faster than the similar recursive
  styled insertion, with and without -O3

  For worst case (sorted array), insertion is 4 times faster, but
  also, still very slow!

  For 10,000 values, insertion takes about 20s for non-recursive
  and 1m 20s for the recursive.
*/

void insertNode(struct node **p, int key)
{
    // don't judge me
    struct node *blarg;
    blarg = NULL;
    int flarg;
    if (*p != NULL)
    {
        blarg = *p; // hang on to the original memory location of the structure
        flarg = 0; // enter into a while loop
    } else {
        flarg = 1; // don't enter the while loop
        *p = malloc(sizeof(struct node));
        (*p)->key = key;
        (*p)->l = NULL;
        (*p)->r = NULL;
    }

    // honey badger don't care
    while (flarg != 1)
    {
        if (key < (*p)->key)
        {
            if ((*p)->l == NULL)
            {
                (*p)->l = malloc(sizeof(struct node));
                flarg = 1;
                *p = (*p)->l;
            } else {
                *p = (*p)->l;
            }
        } else {
            if ((*p)->r == NULL)
            {
                (*p)->r = malloc(sizeof(struct node));
                flarg = 1;
                *p = (*p)->r;
            } else {
                *p = (*p)->r;
            }
        }
        if (flarg == 1)
        {
            (*p)->key = key;
            (*p)->l = NULL;
            (*p)->r = NULL;
        }
    }
    // honey badger don't give a fuck!
    if (blarg != NULL)
    {
        *p = blarg;
    }
    // will work on making all of this less of a steaming pile later
}
struct node *searchTree(struct node *p, int key)
{
    struct node *orig, *copy;
    orig = *p;
    while (*p != NULL && key != (*p)->key)
        *p = (key < (*p)->key) ? (*p)->l : (*p)->r;
    copy = *p;
    *p = orig;
    return copy;
}
void removeNode(struct node **p, int key)
{
    struct node *c, *x, *t, *pr;

    pr = *p;
    x = *p;
    while (key != x->key)
    {
        pr = x; x = (key < x->key) ? x->l : x->r;
    }

    t = x;
    if (t->r == NULL) x = x->l;
    else if (t->r->l == NULL)
    {
        x = x->r;
        x->l = t->l;
    } else {
        c = x->r;
        while (c->l->l != NULL)
            c = c->l;
        x = c->l;
        c->l = x->r;
        x->l = t->l;
        x->r = t->r;
    }
    free(t);
    if (key < pr->key) pr->l = x; else pr->r = x;
}
void printAll(struct node* p)
{
    if (p != NULL)
    {
        printAll(p->l);
        printf("key: %d\n", p->key);
        printAll(p->r);
    }
}
/*
  could be a lot prettier
-2
 |-4
 | |-10
 |    `-7
 |      |-9
 |        `-8
 |      `-6
 |        `-5
 |  `-3
 `-1
-----------------
-7
 |-10
 | `-9
 |    `-8
 `-3
 ` |-6
     `-5
       `-4
   `-2
     `-1
*/
void asciiTree(struct node *p, char *buffer)
{
    char tmpbuff[256];
    int buflen;
    char rchar = '|';
    //strcpy(tmpbuff, buffer);
    buflen = strlen(buffer);
    if (p != NULL)
    {
        printf("%s-%d\n", buffer, p->key);
        if (buflen > 3)
        {
            buffer[buflen-3] = '\0';
            if (p->l == NULL)
                rchar = '`';
            strcat(buffer, "    ");
            strcat(buffer, &rchar);
            asciiTree(p->r, buffer);
            buffer[buflen-3] = '\0';
            asciiTree(p->l, strcat(buffer, "    `"));
        } else {
            if (p->l == NULL)
                rchar = '`';
            strcat(buffer, " ");
            strcat(buffer, &rchar);
            asciiTree(p->r, buffer);
            buffer[buflen] = '\0';
            asciiTree(p->l, strcat(buffer, " `"));
        }
    }
}
int main()
{
    struct node *head;
    char buffer[256];
    buffer[0] = '\0';
    head = NULL;
    struct numbers myNumbers = generateRandoms(-11, 1000);
    int i;
    for (i = 0; i < myNumbers.size; i++)
        insertNode(&head, myNumbers.values[i]);
    struct node *x;
    x = searchTree(&head, -100);
    if (x != NULL)
        printf("found: %d\n", x->key);
    else
        printf("no value found\n");
    asciiTree(head, buffer);
    return 0;
}