Level order traversal (binary tree)

Level order visits every node at depth d before any node at depth d+1. It is exactly BFS on the tree graph: use a queue of node pointers, dequeue the front, print it, enqueue non-null children.

1) Algorithm

2) Example in C

Simple queue-based level order traversal for the tree shown in comments.

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

// Tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Create new 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;
}

// Simple queue
struct Queue {
    struct Node* arr[100];
    int front, rear;
};

// Initialize queue
void initQueue(struct Queue* q) {
    q->front = 0;
    q->rear = -1;
}

// Check empty
int isEmpty(struct Queue* q) {
    return q->front > q->rear;
}

// Enqueue
void enqueue(struct Queue* q, struct Node* node) {
    q->rear++;
    q->arr[q->rear] = node;
}

// Dequeue
struct Node* dequeue(struct Queue* q) {
    return q->arr[q->front++];
}

// Level Order Traversal
void levelOrder(struct Node* root) {
    if (root == NULL) return;

    struct Queue q;
    initQueue(&q);

    enqueue(&q, root);

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

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

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

// Main function
int main() {
    /*
            1
          /   \
         2     3
        / \   /
       4   5 6
    */

    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);

    printf("Level Order Traversal: ");
    levelOrder(root);

    return 0;
}

Step-by-step execution table

How to read this

• Queue column shows current elements waiting to be processed.
• Dequeued node is the one being printed.
• Enqueued nodes are its children added to queue.
• Traversal goes level by level (left to right).

Final output

1 2 3 4 5 6

3) Complexity

• Time: each node enqueued and dequeued once → O(n) for n nodes.
• Extra space: queue holds at most one full level → O(w) width, worst O(n) for a complete last level.