C Program to Implement Level Order Traversal in a Binary Tree

C Program to Implement Level Order Traversal in a Binary Tree

By /

Level order traversal is a method of visiting nodes in a binary tree level by level from top to bottom and from left to right. It uses a queue to keep track of nodes that need to be visited. This traversal is also called Breadth-First Traversal (BFS) because it explores each level fully before moving to the next.

Understanding the Problem

In a binary tree, level order traversal ensures that we process all nodes of depth d before moving to depth d+1. This requires a queue to store child nodes while visiting each parent. Without a queue, it becomes difficult to properly maintain the order of traversal. This method is widely used in problems involving shortest paths, searching, and hierarchical structures.

Program: Level Order Traversal in a Binary Tree

This program demonstrates how to perform level order traversal using a queue to process nodes level by level.

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

// Structure for a tree node
typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

// Structure for a queue
typedef struct Queue {
    Node **arr;
    int front, rear, size, capacity;
} Queue;

// Function to create a new node
Node* createNode(int value) {

    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

// Function to create a queue
Queue* createQueue(int capacity) {

    Queue *q = (Queue*)malloc(sizeof(Queue));
    q->capacity = capacity;
    q->front = q->size = 0;
    q->rear = capacity - 1;
    q->arr = (Node**)malloc(capacity * sizeof(Node*));

    return q;

}

// Check if queue is empty
int isEmpty(Queue *q) {
    return (q->size == 0);
}

// Enqueue operation
void enqueue(Queue *q, Node *node) {

    if (q->size == q->capacity) return; // Overflow condition

    q->rear = (q->rear + 1) % q->capacity;
    q->arr[q->rear] = node;
    q->size++;

}

// Dequeue operation
Node* dequeue(Queue *q) {

    if (isEmpty(q)) return NULL;

    Node *node = q->arr[q->front];

    q->front = (q->front + 1) % q->capacity;
    q->size--;

    return node;

}

// Function for level order traversal
void levelOrderTraversal(Node *root) {

    if (!root) return;

    Queue *q = createQueue(100);
    enqueue(q, root);

    while (!isEmpty(q)) {

        Node *current = dequeue(q);
        printf("%d ", current->data);

        if (current->left)
            enqueue(q, current->left);

        if (current->right)
            enqueue(q, current->right);

    }

    free(q->arr);
    free(q);

}

int main() {

    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 Binary Tree: ");

    levelOrderTraversal(root);

    printf("\n");

    return 0;

}

In this program, a Node structure represents tree nodes, and a Queue structure helps manage nodes during traversal. The root node is inserted into the queue first. Then, nodes are processed one by one: each node is dequeued, printed, and its left and right children are enqueued. This ensures all nodes at the current level are processed before moving to the next.

FAQs

Q1: Is level order traversal the same as BFS?
Yes, level order traversal is a BFS applied specifically to binary trees.

Q2: What is the time complexity of level order traversal?
O(n), since each node is enqueued and dequeued exactly once.

Q3: Do we always need a queue for level order traversal?
Yes, a queue is the simplest and most efficient way to implement it. Recursive approaches exist but are less efficient.

Q4: Can we print level by level instead of a single sequence?
Yes, by keeping track of the number of nodes at each level, you can print them on separate lines.

Conclusion

Level order traversal is an essential technique for binary trees, ensuring that nodes are visited level by level. By using a queue, we can implement this traversal efficiently. This method forms the foundation of many real-world applications like scheduling, network broadcasting, and shortest path algorithms.

References & Additional Resources

A curated list of textbooks and online tutorials for understanding binary trees, level order traversal, and related data structures in C.

  1. Thareja, R. (2011). Data Structures Using C. Oxford University Press – Comprehensive coverage of binary trees, traversal techniques, and memory management.
  2. Programiz: Data Structures – Binary Tree – Beginner-friendly guide on binary tree implementation, including insertion, deletion, and traversal.
  3. GeeksforGeeks: Level Order Traversal of Binary Tree – Explanation and examples of breadth-first traversal (level order) in C.

Related Posts

Scroll to Top