This C program demonstrates how to perform a level order traversal on a binary tree, processing nodes level by level from top to bottom and left to right.

Program Explanation

The program is structured into several parts:

• Node Structure: Defines the structure of a binary tree node.
• Queue Structure: Supports the level order traversal by storing nodes to be processed.
• Function to Create a New Node: Allocates a new node with given data.
• Queue Functions: Includes functions to enqueue and dequeue nodes, as well as to check if the queue is empty.
• Function to Perform Level Order Traversal: Uses the queue to traverse and print the tree level by level.
• Main Function: Demonstrates the level order traversal by creating a binary tree and performing the traversal.

Program Code

// Include necessary headers
#include <stdio.h>
#include <stdlib.h>

// Define the structure for tree nodes
typedef struct node {
    int data;
    struct node* left;
    struct node* right;
} Node;

// Define the structure for queue nodes
typedef struct queueNode {
    Node* treeNode;
    struct queueNode* next;
} QueueNode;

// Function to create a new tree node
Node* newNode(int data) {
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

// Function to enqueue a node
void enqueue(QueueNode** head, Node* treeNode) {
    QueueNode* newQueueNode = (QueueNode*)malloc(sizeof(QueueNode));
    newQueueNode->treeNode = treeNode;
    newQueueNode->next = NULL;

    if (*head == NULL) {
        *head = newQueueNode;
    } else {
        QueueNode* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newQueueNode;
    }
}

// Function to dequeue a node
Node* dequeue(QueueNode** head) {
    if (*head == NULL) return NULL;

    Node* treeNode = (*head)->treeNode;
    QueueNode* temp = *head;
    *head = (*head)->next;
    free(temp);
    return treeNode;
}

// Function to check if the queue is empty
int isEmpty(QueueNode* head) {
    return head == NULL;
}

// Function to perform level order traversal
void levelOrder(Node* root) {
    if (root == NULL) return;

    QueueNode* queue = NULL;
    enqueue(&queue, root);

    while (!isEmpty(queue)) {
        Node* current = dequeue(&queue);
        printf("%d ", current->data);

        if (current->left != NULL) {
            enqueue(&queue, current->left);
        }
        if (current->right != NULL) {
            enqueue(&queue, current->right);
        }
    }
    printf("\\n");
}

// Main function
int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("Level order traversal of binary tree is: ");
    levelOrder(root);

    return 0;
}
    

Key Components of the Program:

• Node and QueueNode Structures: Defines the structure of the binary tree nodes and the nodes used in the queue for level order traversal.
• newNode Function: Allocates and initializes a new tree node.
• Queue Functions (enqueue, dequeue, isEmpty): Manage the queue operations needed for storing nodes during the traversal.
• levelOrder Function: Implements the level order traversal logic using a queue, processing each node and its children.
• Main Function: Sets up a binary tree, invokes the level order traversal function, and prints the traversal results.

This structured approach ensures a clear separation of functionality and demonstrates effective use of basic data structures to achieve the desired traversal of a binary tree.