C Level Order Traversal 🎯

Welcome to your C programming journey! Today, we're diving into an exciting topic: Level Order Traversal. This technique allows us to visit nodes in a binary tree in a specific order, which is essential for many real-world applications. Let's get started!

What is Binary Tree? 📝

Before we delve into Level Order Traversal, let's understand what a binary tree is. A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.

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

Level Order Traversal 💡

Level Order Traversal, also known as Breadth-First Traversal (BFS), is a tree traversal method where we visit nodes at the same level in the tree from left to right before moving to the next level.

Algorithm

Create a queue to hold nodes.
Initialize the queue with the root node.
While the queue is not empty:
- Dequeue a node from the front of the queue.
- Print the value of the dequeued node.
- Enqueue the left child of the dequeued node, if it exists.
- Enqueue the right child of the dequeued node, if it exists.
Stop when the queue is empty.

Example

Here's a simple example of Level Order Traversal:

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

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

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

void levelOrderTraversal(struct Node* root) {
    if (root == NULL)
        return;

    struct Node* currentNode = root;
    struct Node* nextLevelNodes[1000];
    int nextLevelNodesIndex = 0;

    printf("%d ", root->data);

    nextLevelNodes[nextLevelNodesIndex++] = root->left;
    nextLevelNodes[nextLevelNodesIndex++] = root->right;

    while (nextLevelNodesIndex > 0) {
        currentNode = nextLevelNodes[0];
        printf("%d ", currentNode->data);

        if (currentNode->left)
            nextLevelNodes[nextLevelNodesIndex++] = currentNode->left;
        if (currentNode->right)
            nextLevelNodes[nextLevelNodesIndex++] = currentNode->right;

        currentNode = NULL;
        nextLevelNodesIndex--;
    }
}

int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Level Order Traversal:\n");
    levelOrderTraversal(root);

    return 0;
}

Now that you've learned Level Order Traversal, you can explore more complex binary trees and optimize your C programs to handle them effectively! Happy coding! 🚀💻