Segmentation fault, while dequeuing

Question

I'm quite new to DS and I'm trying to implement binary tree level order traversal using a queue. The algorithm is as below.

1. Get the root of the tree
2. detached_node = root
3. while detached_node:
   • print detached_node->data
   • Enqueue detached_node->left and detached_node->right, if not NULL
   • detached_node = dequeue()

I'm getting segmentation fault in dequeue(). Here's the gdb core dump.

gdb main core
GNU gdb (Ubuntu 8.1-0ubuntu3.2) 8.1.0.20180409-git
This GDB was configured as "x86_64-linux-gnu".
(gdb) r
Starting program: /home/runner/DryPartialNetbsd/main 
warning: Error disabling address space randomization: Operation not permitted
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Program received signal SIGSEGV, Segmentation fault.
0x00000000004006d3 in dequeue ()

I'm not sure what I'm missing here and I'm trying to understand.

Below is the code

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

struct t_node {
    int data;
    struct t_node* left;
    struct t_node* right;
};

struct t_node* create_t_node(int value) {
    struct t_node* node = (struct t_node*) malloc(sizeof(struct t_node));
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct q_node {
    struct t_node* data;
    struct q_node* next;
};

struct q_node* rear = NULL;
struct q_node* front = NULL;

struct q_node* create_q_node(struct t_node* value) {
    struct q_node* node = (struct q_node*) malloc(sizeof(struct q_node));
    node->data = value;
    node->next = NULL;
    return node;
}

void create_queue(struct t_node* value) {
    struct q_node* node = create_q_node(value);
    front = node;
    rear = node;
}

void enqueue(struct t_node* value) {
    if (front == NULL && rear == NULL) {
        create_queue(value);
    } else {
        struct q_node* node = create_q_node(value);
        rear->next = node;
        front->next = node;
        rear = node;
    }
}

struct t_node* dequeue() {
    if(rear == NULL && front == NULL) 
        return NULL;
    else {
        struct q_node* node = front;
        front = front->next;
        return node->data; 
    }
}

void print_level_order(struct t_node* root) {
    if(root == NULL) {
        return;
    }
    struct t_node* detached_node = root;
    while(detached_node != NULL) {
        printf("%d ", detached_node->data);
        if(detached_node->left != NULL) {
            enqueue(detached_node->left);
        }
        if(detached_node->right != NULL) {
            enqueue(detached_node->right);
        }
        detached_node = dequeue();
    }
}

int main(void) {
    struct t_node* root = create_t_node(1);
    root->left = create_t_node(2);
    root->right = create_t_node(3);
    root->left->left = create_t_node(4);
    root->left->right = create_t_node(5);
    root->right->left = create_t_node(6);
    root->right->right = create_t_node(7);
    
    print_level_order(root);
}

Answer 1

Your problem comes because you update rear and front when you enqueue but you only update front when you dequeue, so in dequeue :

if(rear == NULL && front == NULL)

cannot be true if you enqueue at least one time before making rear non NULL, then after enough dequeue you do :

front = front->next;

when front is NULL

So modify dequeue for instance to be

struct t_node* dequeue() {
    if(rear == NULL && front == NULL) 
        return NULL;
    else {
        struct q_node* node = front;
        front = front->next;
        if (front == NULL)
          rear = NULL;

        struct t_node* result = node->data; 
        
        free(node);
        return result;
    }
}

note you also need to free memory to not have memory leaks

After correction :

pi@raspberrypi:/tmp $ gcc -g -Wall c.c
pi@raspberrypi:/tmp $ ./a.out
1 2 3 5 7 pi@raspberrypi:/tmp $