Level Order Binary Tree Traversal Implementation with Queue

Question

I am trying to implement a levelOrder funtion which takes pointer of tree and prints the data of tree level-by-level. This is a question from the book C How to Program and the full question is given below:

(Level Order Binary Tree Traversal) The program of Fig. 12.19 illustrated three recursive methods of traversing a binary tree—inorder traversal, preorder traversal, and postorder traversal. This exercise presents the level order traversal of a binary tree in which the node values are printed level-by-level starting at the root node level. The nodes on each level are printed from left to right. The level order traversal is not a recursive algorithm. It uses the queue data structure to control the output of the nodes. The algorithm is as follows:

1. Insert the root node in the queue

2. While there are nodes left in the queue,

   Get the next node in the queue

   Print the node’s value

   If the pointer to the left child of the node is not NULL Insert the left child node in the queue

   If the pointer to the right child of the node is not NULL
   Insert the right child node in the queue.

Write function levelOrder to perform a level order traversal of a binary tree. The function should take as an argument a pointer to the root node of the binary tree. Modify the program of Fig. 12.19 to use this function. Compare the output from this function to the outputs of the other traversal algorithms to see that it worked correctly. [Note: You’ll also need to modify and incor- porate the queue-processing functions of Fig. 12.13 in this program.]

My try is below:

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

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

struct queueNode{
    struct treeNode* tree;
    struct queueNode* next;
};


/* prototype */
void insert(struct treeNode**, int); // tree creator
void levelOrder(struct treeNode**);
void inOrder(struct treeNode*);
void enqueue(struct queueNode**, struct queueNode**, struct treeNode*);
struct treeNode* dequeue(struct queueNode**, struct queueNode**);

int main(){
    struct treeNode* root = NULL;
    levelOrder(&root);
}

void insert(struct treeNode** root, int val){
    if(!(*root)){ // when root is empty
        *root = (struct treeNode*)malloc(sizeof(struct treeNode));
        if(*root){ // if allocation is achieved
            (*root) -> data = val;
            (*root) -> right = NULL;
            (*root) -> left = NULL;
        } else { // if allocation is not succesfull
            printf("%s\n", "[ERROR] Not enough memory space for allocation!");
        }
    } else { // if root is not empty
        if(val > (*root) -> data)
            insert(&(*root) -> right, val);
        else if(val < (*root) -> data)
            insert(&(*root) -> left, val);
    }
}

void enqueue(struct queueNode** head, struct queueNode** tail, struct treeNode* tree){
    struct queueNode* newNode = (struct queueNode*)malloc(sizeof(struct queueNode));
    if( newNode ){
        newNode -> tree = tree;
        newNode -> next = NULL;
        if(!(*head)){
            *head = newNode;
            //printf("head->tree->data:%d --> ", (*head)->tree->data);
            printf("%d --> ", (*head)->tree->data);
        }
        else{
            (*tail) -> next = newNode;
            //printf("tail->tree->data:%d --> ", (*tail)->tree->data);
            printf("%d --> ", (*tail)->tree->data);
        }
        (*tail) = newNode;
    } else {
        printf("%s\n", "[ERROR] Not enough memory space for allocation!");
    }
}

struct treeNode* dequeue(struct queueNode** head, struct queueNode** tail){
    struct treeNode* val = (*head)->tree;
    struct queueNode* temp = *head;
    *head = (*head) -> next;
    if(!(*head))
        *tail = NULL;
    return val;
}

void levelOrder(struct treeNode** root){
    struct treeNode* output = NULL;
    struct queueNode* head = NULL, *tail = NULL;
    size_t i;
    srand(time(NULL));
    for(i = 0; i < 9; ++i){
        insert(root, 1 + rand()%16);
    }
    puts("in order");
    inOrder(*root);
    puts("NULL");
    puts("After in order");
    enqueue(&head, &tail, *root);
    while(head){
        if(head->tree->left)
            enqueue(&head, &tail, head->tree->left);
        if(head->tree->right)
            enqueue(&head, &tail, head->tree->right);
        head = head->next;
    }


    /*for(i=0;i<9;++i){
       output = dequeue(&head, &tail);
       printf("%d",output->data);
    }*/
}

void inOrder(struct treeNode* tree){ // used to be sure if my implementation works correct
    if(tree != NULL){
        inOrder(tree->left);
        printf("%-2d-->", tree->data);
        inOrder(tree->right);
    }
}

When I use dequeue function, it does not work correctly. I cannot get all trees in the queue with dequeue function. However, if I print the values in enqueue as seen, it prints all the value added except one(I do not which one) but prints the first value twice. (Can you please run the code? I wanted to put the outputs here, but stackoverflow thinks it as a code block and I cannot edit it so it did not let me add it.)

Answer 1

Some issues:

• In enqueue, in the else block, you print the value of tail before it is moved: this may be misleading to the reader of the output, as this value is not the value being appended to the queue. I assume this is for debugging, but in the end you should not print here.

• In the main loop, you should not move the head reference just like that. Instead use dequeue at the start of the loop, and capture the node in the output variable you had already declared, and immediately print the corresponding value. This will keep the queue at a size that is not longer than necessary.

  while(head){
      output = dequeue(&head, &tail); // extract
      printf("%d --> ", output->data); // print here instead of in enqueue
      if(output->left) // use output
          enqueue(&head, &tail, output->left);
      if(output->right)
          enqueue(&head, &tail, output->right);
      // Don't move head here
  }
  puts("\n");
  

• In dequeue you should free the queue node that you removed from the queue, right before return:

  free(temp);
  

Some other remarks:

• levelOrder should not really be responsible for building the tree. Do that in your main driver code, or -- if you really want to -- in a separate function. And then make the second argument to levelOrder just struct treeNode * instead of struct treeNode **.

• For debugging it will be useful that your inOrder implementation prints values on separate lines with an indentation that corresponds to the depth of the recursion, for which you can pass an extra int depth parameter. That way you got a bit of a visual on the actual tree structure.