Binary Tree creation in C

Question

I have created a program to generate a tree using a double-linked list and queues, which are also implemented with the help of a single-linked list. However, I am encountering a problem. When I input, for example, 7, the program prompts for left and right only once, and then it terminates. Upon tracing the program, it should take all inputs properly instead of terminating after just two numbers. I have attempted to debug the program several times, and I am quite frustrated at this point. Could you please check for any issues in the enqueue, dequeue, or create functions, or perhaps in the global declarations? I appreciate your assistance. Thank you

Here is the code:

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

typedef struct tree {
    struct tree *lchild;
    int data;
    struct tree *rchild;
} tree;//create

typedef struct Queue {
    tree *data;
    struct Queue *next;
} Queue;//isEmptyQ,isFullQ,enQueue,deQueue

Queue *f = NULL;
Queue *r = NULL;
tree *root;

int isEmptyQ()
{
    return r == NULL || f == NULL;
}

int isFullQ()
{
    Queue *t = malloc(sizeof(Queue));
    return t == NULL;
}

void enQueue(tree *data)
{
    if (!isFullQ())
    {
        Queue *t = malloc(sizeof(Queue));
        t->data = data;
        t->next = NULL;  // Initialize next pointer to NULL

        if (r == NULL && f == NULL)
        {
            r = f = t;
        }
        else
        {
            r->next = t;
            r = t;
        }
    }
}

tree *deQueue()
{
    if (!isEmptyQ())
    {
        Queue *temp = f;
        tree *t = f->data;
        f = f->next;
        free(temp);
        return t;
    }
    return NULL;
}

void create()
{
    root = malloc(sizeof(tree));
    int data;
    printf("Enter the data to be entered:");
    scanf("%d", &data);
    root->data = data;
    root->lchild = root->rchild = NULL;
    enQueue(root);

    tree *p = NULL;
    while (!isEmptyQ())
    {
        p = deQueue();
        printf("Left? of %d (-1 for no left child):", p->data);
        scanf("%d", &data);
        if (data != -1)
        {
            tree *t = malloc(sizeof(tree));
            t->data = data;
            t->lchild = t->rchild = NULL;
            p->lchild = t;
            enQueue(t);
        }

        printf("Right? of %d (-1 for no right child):", p->data);
        scanf("%d", &data);
        if (data != -1)
        {
            tree *t = malloc(sizeof(tree));
            t->data = data;
            t->lchild = t->rchild = NULL;
            p->rchild = t;
            enQueue(t);
        }
    }
}

int main()
{
    create();
}

Answer 1

Your dequeue function seems to lack proper handling of the case where the queue gets empty.

As far as I can see the two global(!) variables f and r represent front and rear of a linked list.

When doing dequeue of the front element you will "normally" only need to update the value of f. However, there is a special case when the linked list only contains a single element. In that case, you need to update both f and r.

So after changing f check whether r needs to be updated. Perhaps like:

f = f->next;               // existing line
if (f == NULL) r = NULL;   // add this line

Further, you should reconsider the function isFullQ. Currently it leaks memory as the malloced memory isn't returned nor freed. That's a bug. In any case you can't check for "out of memory" like that. It makes no sense at all. Instead you need to check for NULL after all mallocs.

BTW: Use of global variables are in most cases a bad idea. In small "toy" programs you can do it but in bigger programs it will soon become very difficult to read, understand and maintain the code. Avoid global variables unless you have a very, very good reason.