Binary Tree Level-Wise Creation and Traversal

Question

I have used a queue, which has been implemented using a singly linked list, to facilitate the level-wise creation and traversal of the binary tree.

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


typedef struct tree_node
{
    int num;
    struct tree_node* left_child;
    struct tree_node* right_child;
} Tree_Node;

void free_tree(Tree_Node*);


typedef struct queue_node
{
    Tree_Node** ptr_ptr_current_tree_node;
    struct queue_node* next;
} Queue_Node;

void enqueue(Tree_Node**);
Tree_Node** peek(void);
void dequeue(void);
bool is_empty(void);

Queue_Node* front = NULL;   // front means ptr_front_queue_node


int main(void)
{

    Tree_Node* root = NULL;   // root means ptr_root_tree_node
    enqueue(&root);

    int num;

    printf("Enter integers (q to quit) :-\n");
    printf(">>> ");

    while (scanf("%d", &num) == 1)
    {
        Tree_Node** ptr_ptr_current_tree_node = peek();
        dequeue();

        (*ptr_ptr_current_tree_node) = malloc(sizeof (Tree_Node));
        if (*ptr_ptr_current_tree_node == NULL)
        {
            fprintf(stderr, "Unsuccessful allocation\n");
            exit(EXIT_FAILURE);
        }
        (*ptr_ptr_current_tree_node)->num = num;

        (*ptr_ptr_current_tree_node)->left_child = NULL;
        enqueue(&((*ptr_ptr_current_tree_node)->left_child));

        (*ptr_ptr_current_tree_node)->right_child = NULL;
        enqueue(&((*ptr_ptr_current_tree_node)->right_child));

        printf(">>> ");
    }
    printf("\n");

    while (!(is_empty()))
        dequeue();


    enqueue(&root);
    enqueue(NULL);

    while (true)
    {
        Tree_Node** ptr_ptr_current_tree_node = peek();
        dequeue();

        if (ptr_ptr_current_tree_node)
        {
            if (*ptr_ptr_current_tree_node == NULL)
            {
                printf("\n");
                break;
            }

            else
            {
                printf("%d ", (*ptr_ptr_current_tree_node)->num);
                enqueue(&((*ptr_ptr_current_tree_node)->left_child));
                enqueue(&((*ptr_ptr_current_tree_node)->right_child));
            }
        }

        else
        {
            printf("\n");
            enqueue(NULL);
        }
    }

    while (!(is_empty()))
        dequeue();


    free_tree(root);

    return 0;

}


void free_tree(Tree_Node* ptr_current_tree_node)
{

    if (ptr_current_tree_node)
    {
        if (ptr_current_tree_node->left_child)
            free_tree(ptr_current_tree_node->left_child);
        if (ptr_current_tree_node->right_child)
            free_tree(ptr_current_tree_node->right_child);
        free(ptr_current_tree_node);
    }

}


void enqueue(Tree_Node** ptr_ptr_current_tree_node)
{

    Queue_Node* new = malloc(sizeof (Queue_Node));
    if (new == NULL)
    {
        fprintf(stderr, "Unsuccessful allocation\n");
        exit(EXIT_FAILURE);
    }
    new->ptr_ptr_current_tree_node = ptr_ptr_current_tree_node;

    if (front == NULL)
    {
        front = new;
    }

    else
    {
        Queue_Node* current = front;
        while (current->next)
            current = current->next;
        current->next = new;
    }

    new->next = NULL;

}


Tree_Node** peek(void)
{

    return (front->ptr_ptr_current_tree_node);

}


void dequeue(void)
{

    Queue_Node* temp_node = front;
    front = front->next;
    free(temp_node);

}


bool is_empty(void)
{

    return (front == NULL);

}
```

Answer 1

The code is generally very readable and maintainable. You have a very good start on a data structure library, but I would suggest that the binary tree deserves as much attention as the queue got. For program organization I would suggest that the queue functions and the tree functions each should have their own C implementation file and header file. The header file should contain the node declarations and any function prototypes.

It is not clear why you chose to have a queue of tree nodes rather than just a queue of integers, there is no need for the 2 data structures to know about each other.

In the first major loop in main() it would be better use return from main rather than exit(), the exit() function is only needed when a C program has to terminate from a function other than main().

Avoid Global Variables

The queue front variable is a global variable, it would be better if it was declared in the main function rather than as a global variable. It is very difficult to read, write, debug and maintain programs that use global variables. Global variables can be modified by any function within the program and therefore require each function to be examined before making changes in the code. In C and C++ global variables impact the namespace and they can cause linking errors if they are defined in multiple files. The answers in this stackoverflow question provide a fuller explanation.

Complexity

The function main() is too complex (does too much). As programs grow in size the use of main() should be limited to calling functions that parse the command line, calling functions that set up for processing, calling functions that execute the desired function of the program, and calling functions to clean up after the main portion of the program.

There is also a programming principle called the Single Responsibility Principle that applies here. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

Each of the multi-line while loops in the main() function should be a function called by main().

The following code is an example it is not completely correct.

Queue_Node* get_input()
{
    int num;

    printf("Enter integers (q to quit) :-\n");
    printf(">>> ");

    while (scanf("%d", &num) == 1)
    {
        Tree_Node** ptr_ptr_current_tree_node = peek();
        dequeue();

        (*ptr_ptr_current_tree_node) = malloc(sizeof(Tree_Node));
        if (*ptr_ptr_current_tree_node == NULL)
        {
            fprintf(stderr, "Unsuccessful allocation\n");
            exit(EXIT_FAILURE);
        }
        (*ptr_ptr_current_tree_node)->num = num;

        (*ptr_ptr_current_tree_node)->left_child = NULL;
        enqueue(&((*ptr_ptr_current_tree_node)->left_child));

        (*ptr_ptr_current_tree_node)->right_child = NULL;
        enqueue(&((*ptr_ptr_current_tree_node)->right_child));

        printf(">>> ");
    }
    printf("\n");

    return front;
}

Tree_Node* build_tree(Queue_Node* front)
{
    Tree_Node* root;

    while (true)
    {
        Tree_Node** ptr_ptr_current_tree_node = peek();
        dequeue();

        if (ptr_ptr_current_tree_node)
        {
            if (*ptr_ptr_current_tree_node == NULL)
            {
                printf("\n");
                break;
            }

            else
            {
                printf("%d ", (*ptr_ptr_current_tree_node)->num);
                enqueue(&((*ptr_ptr_current_tree_node)->left_child));
                enqueue(&((*ptr_ptr_current_tree_node)->right_child));
            }
        }

        else
        {
            printf("\n");
            enqueue(NULL);
        }
    }

    return root;
}

int main(void)
{

    Tree_Node* root = NULL;   // root means ptr_root_tree_node
    enqueue(&root);

    front = get_input();

    while (!(is_empty()))
        dequeue();


    enqueue(&root);
    enqueue(NULL);

    root = build_tree(front);

    while (!(is_empty()))
        dequeue();


    free_tree(root);

    return 0;

}
```