Binary tree level order traversal with Queue stuck in infinite loop

Question

I have been trying to implement binary tree with queue in C and I am fairly new to this language. I have been trying to debug the code I have written in C, wrote the code from scratch but with no fruit. I can not see what am I doing wrong.

I checked the queue code that I wrote with integer data and it worked perfectly.

enqueue function pushes an element in the queue
dequeue function pops an element from the queue
empty function check if queue is empty

Then I implemented Binary Search Tree and printed the elements in the node with

root -> left -> left -> left -> data; //worked fine, was able to reach the extreme left leaf node

and

root -> right -> right -> right -> data; //worked fine, just in case

and some more traversals like this and it seems the tree formed fine. I printed the queue in level_order() function and what I could understand was queue was not building right. Somehow the whole thing goes into infinite loop. I have ran out of ideas. Here's the code, thanks.

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

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

struct Queue{
    struct BstNode *address;
    struct Queue *next;
};

struct Queue *front = NULL;
struct Queue *back = NULL;

struct Queue* create_queue(BstNode **address){
    struct Queue *temp = (Queue*)malloc(sizeof(struct Queue));
    temp -> next = NULL;
    temp -> address = *address;
    return temp;
}

void enqueue(BstNode **address){
    struct Queue *temp = create_queue(address);
    if(front == NULL && back == NULL){
        front = back = temp;
    }
    else{
        temp -> next = back;
        back = temp;
    }
}

void dequeue(){
    if(front == NULL){
        return;
    }
    struct Queue* temp;
    temp = back;
    if(front == back){
        front = back = NULL;
    }
    else{
        back = back -> next;
    }
    free(temp);
}

bool empty(){
    if(front == NULL){
        return true;
    }
    return false;
}

void print_queue(){
    struct Queue *temp = back;
    while(temp != NULL){
        printf("%d", temp->address->data);
        temp = temp -> next;
    }
    printf("\n");
}

struct BstNode *root;

struct BstNode *create_node(int data){
    struct BstNode *temp = (BstNode *)malloc(sizeof(struct BstNode));
    temp -> data = data;
    temp -> left = NULL;
    temp -> right = NULL;
    return temp;
}

void insert_bst_cell(BstNode **node, int data){
    if((*node) == NULL){
        struct BstNode* temp = create_node(data);
        *node = temp;
    }
    else if(data > (*node)->data){
        insert_bst_cell(&(*node)->right, data);
    }
    else if(data < (*node)->data){
        insert_bst_cell(&(*node)->left, data);
    }
}

BstNode *first_element(){
    return front->address;
}

void level_order(){
    if(root == NULL) return;
    enqueue(&root);
    while(!(empty())){
        struct BstNode *current = first_element();
        dequeue();
        printf("%d\n", current->data);
        if(current->right != NULL){
            enqueue(&(current->left));
        }
        if(current->left != NULL){
            enqueue(&(current->right));
        }
    }
}

int main(int argc, char **argv)
{
    front = NULL;
    back = NULL;
    root = NULL;
    insert_bst_cell(&root, 15);
    insert_bst_cell(&root, 10);
    insert_bst_cell(&root, 20);
    insert_bst_cell(&root, 5);
    insert_bst_cell(&root, 11);
    insert_bst_cell(&root, 17);
    insert_bst_cell(&root, 25);
    insert_bst_cell(&root, 4);
    insert_bst_cell(&root, 6);
    insert_bst_cell(&root, 9);
    insert_bst_cell(&root, 12);
    insert_bst_cell(&root, 16);
    insert_bst_cell(&root, 19);
    insert_bst_cell(&root, 21);
    insert_bst_cell(&root, 35);
    level_order();
    return 0;
}

Please [Don't cast malloc](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) in C... — Serge Ballesta, Jan 30 '18 at 15:59
This is more or less C code compiled with a C++ compiler. In other words: it compiles with a C++ compiler but it does not compile with a C compiler. BTW you forgot the `#include #include ` — Jabberwocky, Jan 30 '18 at 16:02
We could really use an accurate problem description: where is the infinite loop, what are the critical variable values there, and what does the tree *really* look like at that point? — Prune, Jan 30 '18 at 16:21
Did you test your queue implementation? I think it's a stack and not a queue. That should not explain the infinite loop though. — Paul Georg Podlech, Jan 30 '18 at 17:02
I'll check the queue implementation, thanks for pointing that out — Sushant, Jan 30 '18 at 17:22

score 1 · Accepted Answer · answered Jan 30 '18 at 18:32

Thanks to Paul Georg Podlech for pointing it out that I had implemented a stack instead of queue. The other mistake was

if(current->right != NULL){
    enqueue(&(current->left));
}
if(current->left != NULL){
    enqueue(&(current->right));
}

in this particular code. It should be

if(current->left != NULL){    //current -> right in previous snippet
    enqueue(&(current->left));  
}
if(current->right != NULL){    //current -> left in previous snippet
    enqueue(&(current->right));
}

And just in case I'll post the working code

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

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

struct Queue{
    struct BstNode *address;
    struct Queue *next;
};

struct Queue *front = NULL;
struct Queue *back = NULL;

struct Queue* create_queue(BstNode **address){
    struct Queue *temp = (Queue*)malloc(sizeof(struct Queue));
    temp -> next = NULL;
    temp -> address = *address;
    return temp;
}

void enqueue(BstNode **address){
    struct Queue *temp = create_queue(address);
    if(front == NULL && back == NULL){
        front = back = temp;
    }
    else{
//        temp -> next = back;
        back -> next = temp;
        back = temp;
    }
}

void dequeue(){
    if(front == NULL){
        return;
    }
    struct Queue* temp;
    temp = front;
    if(front == back){
        front = back = NULL;
    }
    else{
        front = front -> next;
    }
    free(temp);
}

bool empty(){
    if(front == NULL){
        return true;
    }
    return false;
}

void print_queue(){
    struct Queue *temp = back;
    while(temp != NULL){
        printf("%d", temp->address->data);
        temp = temp -> next;
    }
    printf("\n");
}

struct BstNode *root;

struct BstNode *create_node(int data){
    struct BstNode *temp = (BstNode *)malloc(sizeof(struct BstNode));
    temp -> data = data;
    temp -> left = NULL;
    temp -> right = NULL;
    return temp;
}

void insert_bst_cell(BstNode **node, int data){
    if((*node) == NULL){
        struct BstNode* temp = create_node(data);
        *node = temp;
    }
    else if(data > (*node)->data){
        insert_bst_cell(&(*node)->right, data);
    }
    else if(data < (*node)->data){
        insert_bst_cell(&(*node)->left, data);
    }
}

BstNode *first_element(){
    return front->address;
}

void level_order(){
    if(root == NULL) return;
    enqueue(&root);
    while(!(empty())){
        struct BstNode *current = first_element();
        dequeue();
        printf("%d\n", current->data);
        if(current->left != NULL){
            enqueue(&(current->left));
        }
        if(current->right != NULL){
            enqueue(&(current->right));
        }
    }
}

int main(int argc, char **argv)
{
    front = NULL;
    back = NULL;
    root = NULL;
    insert_bst_cell(&root, 15);
    insert_bst_cell(&root, 10);
    insert_bst_cell(&root, 20);
    insert_bst_cell(&root, 5);
    insert_bst_cell(&root, 11);
    insert_bst_cell(&root, 17);
    insert_bst_cell(&root, 25);
    insert_bst_cell(&root, 4);
    insert_bst_cell(&root, 6);
    insert_bst_cell(&root, 9);
    insert_bst_cell(&root, 12);
    insert_bst_cell(&root, 16);
    insert_bst_cell(&root, 19);
    insert_bst_cell(&root, 21);
    insert_bst_cell(&root, 35);
    level_order();
    return 0;
}

Thank you everyone for their valuable time and input.

Binary tree level order traversal with Queue stuck in infinite loop

1 Answers1