[Join Our Blog]

DSA Series Chapter 16 – LEVEL ORDER TRAVERSAL(BINARY TREE BFS)(C Version)

Objective of this Post

This post explains Level Order Traversal of a Binary Tree using Breadth First Search (BFS).
Key focus:
Queue-based traversal logic
Difference between BFS and DFS
Practical understanding with dry run

1. What is Level Order Traversal?

Definition (Exam-Ready)

Level Order Traversal is a traversal technique in which nodes of a binary tree are visited level by level from left to right, starting from the root.

Traversal Category

Breadth First Search (BFS)

2. Binary Tree Diagram Used

3. Traversal Order (Level-wise)

Level Nodes Visited
0 1
1 2, 3
2 4, 5

Level	Nodes Visited
0	1
1	2, 3
2	4, 5

Final Output

1 2 3 4 5

4. Algorithm (Plain English)

If tree is empty, stop
Create an empty queue
Insert root node into queue
While queue is not empty:
Remove front node
Visit (print) the node
Enqueue left child (if exists)
Enqueue right child (if exists)

5. Queue Concept Used

FIFO (First In First Out)
Ensures level-by-level traversal

6. C Program – Level Order Traversal (Using Queue)

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

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

struct Queue {
    int front, rear;
    int size;
    struct Node **array;
};

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

struct Queue* createQueue(int size)
{
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->front = queue->rear = 0;
    queue->size = size;
    queue->array = (struct Node**)malloc(size * sizeof(struct Node*));
    return queue;
}

int isEmpty(struct Queue* queue)
{
    return queue->front == queue->rear;
}

void enqueue(struct Queue* queue, struct Node* node)
{
    queue->array[queue->rear++] = node;
}

struct Node* dequeue(struct Queue* queue)
{
    return queue->array[queue->front++];
}

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

    struct Queue* queue = createQueue(100);
    enqueue(queue, root);

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

        if (temp->left != NULL)
            enqueue(queue, temp->left);

        if (temp->right != NULL)
            enqueue(queue, temp->right);
    }
}

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: ");
    levelOrder(root);

    return 0;
}

7. Dry Run (Queue Simulation)

Queue: [1]
Dequeue 1 → print 1 → enqueue 2, 3
Queue: [2, 3]
Dequeue 2 → print 2 → enqueue 4, 5
Queue: [3, 4, 5]
Dequeue 3 → print 3
Queue: [4, 5]
Dequeue 4 → print 4
Queue: [5]
Dequeue 5 → print 5
Queue empty → stop