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);
}
```