Level Order Traversal of Binary Tree

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

// Define the structure for a binary tree node
struct Node {
    int data;
    struct Node *left, *right;
};

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

// Function to print the level order traversal
void levelOrderTraversal(struct Node* root) {
    if (root == NULL)
        return;

    // Create a queue (using an array for simplicity)
    struct Node* queue[100];
    int front = 0, rear = 0;

    // Enqueue the root node
    queue[rear++] = root;

    while (front < rear) {
        // Dequeue a node from the queue
        struct Node* current = queue[front++];
        
        // Print the current node's data
        printf("%d ", current->data);

        // Enqueue the left child if it exists
        if (current->left != NULL)
            queue[rear++] = current->left;

        // Enqueue the right child if it exists
        if (current->right != NULL)
            queue[rear++] = current->right;
    }
}

// Main function to test the above code
int main() {
    // Create the root node and other nodes
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);

    printf("Level Order Traversal of the Binary Tree:\n");
    levelOrderTraversal(root);

    return 0;
}

Explanation:

1. Structure Definition:
   • We define a struct called Node to represent each node in the tree. It has:
     • int data: To store the node’s value.
     • struct Node* left: Pointer to the left child.
     • struct Node* right: Pointer to the right child.
2. Create Node Function:
   • The createNode function allocates memory for a new node, assigns it the provided data, and sets its left and right pointers to NULL (indicating no children initially).
3. Level Order Traversal Function:
   • We handle an empty tree scenario using if (root == NULL) return;.
   • We use an array as a simple queue. The front and rear indices help track the front and back of the queue.
   • Initially, the root node is added to the queue.
   • A while loop runs as long as there are nodes in the queue.
     • We dequeue the front node, print its data, and enqueue its left and right children if they exist.
4. Main Function:
   • Here, we create a sample binary tree and call the levelOrderTraversal function.
   • The tree structure looks like this:

     1
    / \
   2   3
  / \ / \
 4  5 6  7

Output:

Level Order Traversal of the Binary Tree:
1 2 3 4 5 6 7

Explanation of the Output:

• The output reflects the level-by-level order of the binary tree.
• Starting with the root (1), we move to the next level (2 and 3), then to the subsequent level (4, 5, 6, 7).

Key Points:

• Using a queue is essential to maintain the order of nodes as we process them level by level.
• This approach ensures that each node is visited exactly once, making the time complexity O(n), where n is the number of nodes in the tree.
• Memory complexity depends on the maximum number of nodes at any level (breadth of the tree), typically O(width) of the tree.