Tree Traversal Level Order BFS in DSA C

Mental Model

We visit tree nodes level by level from top to bottom, left to right. This way, we see all nodes at one depth before moving deeper.

Analogy: Imagine a group of friends standing in rows. You greet everyone in the first row, then move to the second row, and so on, instead of greeting randomly.

       1
      / \
     2   3
    / \   \
   4   5   6

Queue: []
Start at root (1)

Dry Run Walkthrough

Input: Tree: 1 as root, 2 and 3 as children of 1, 4 and 5 as children of 2, 6 as right child of 3

Goal: Print nodes level by level: 1, then 2 and 3, then 4, 5, and 6

Step 1: Add root node 1 to queue

Queue: [1]
Output: 

Why: Start traversal from the root node

Step 2: Remove 1 from queue and print it; add its children 2 and 3 to queue

Queue: [2, 3]
Output: 1

Why: Visit root, then prepare to visit its children next

Step 3: Remove 2 from queue and print it; add its children 4 and 5 to queue

Queue: [3, 4, 5]
Output: 1 2

Why: Visit next node at level 2 and enqueue its children

Step 4: Remove 3 from queue and print it; add its child 6 to queue

Queue: [4, 5, 6]
Output: 1 2 3

Why: Visit next node at level 2 and enqueue its child

Step 5: Remove 4 from queue and print it; it has no children

Queue: [5, 6]
Output: 1 2 3 4

Why: Visit node at level 3 with no children

Step 6: Remove 5 from queue and print it; it has no children

Queue: [6]
Output: 1 2 3 4 5

Why: Visit node at level 3 with no children

Step 7: Remove 6 from queue and print it; it has no children

Queue: []
Output: 1 2 3 4 5 6

Why: Visit last node at level 3

Result:

Queue: []
Output: 1 2 3 4 5 6

Annotated Code

DSA C

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

// Define tree node
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Create new node
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Queue node for BFS
typedef struct QueueNode {
    Node* treeNode;
    struct QueueNode* next;
} QueueNode;

// Queue structure
typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

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

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

// Enqueue tree node
void enqueue(Queue* q, Node* node) {
    QueueNode* temp = (QueueNode*)malloc(sizeof(QueueNode));
    temp->treeNode = node;
    temp->next = NULL;
    if (q->rear == NULL) {
        q->front = temp;
        q->rear = temp;
        return;
    }
    q->rear->next = temp;
    q->rear = temp;
}

// Dequeue tree node
Node* dequeue(Queue* q) {
    if (isEmpty(q)) return NULL;
    QueueNode* temp = q->front;
    Node* node = temp->treeNode;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
    return node;
}

// Level order traversal function
void levelOrderBFS(Node* root) {
    if (root == NULL) return; // handle empty tree
    Queue q;
    initQueue(&q);
    enqueue(&q, root); // start with root

    while (!isEmpty(&q)) {
        Node* curr = dequeue(&q); // get front node
        printf("%d ", curr->data); // print current node

        if (curr->left != NULL) enqueue(&q, curr->left); // enqueue left child
        if (curr->right != NULL) enqueue(&q, curr->right); // enqueue right child
    }
}

int main() {
    // Build tree from dry run example
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->right = newNode(6);

    levelOrderBFS(root);
    printf("\n");
    return 0;
}

if (root == NULL) return; // handle empty tree

stop if tree is empty

enqueue(&q, root); // start with root

add root node to queue to begin traversal

while (!isEmpty(&q)) {

repeat until all nodes are visited

Node* curr = dequeue(&q); // get front node

remove front node from queue to visit it

printf("%d ", curr->data); // print current node

output current node's value

if (curr->left != NULL) enqueue(&q, curr->left); // enqueue left child

add left child to queue if exists

if (curr->right != NULL) enqueue(&q, curr->right); // enqueue right child

add right child to queue if exists

Output

1 2 3 4 5 6 

Complexity Analysis

Time: O(n) because each node is visited exactly once during traversal

Space: O(n) because in worst case the queue holds all nodes at the largest level

vs Alternative: Compared to recursive DFS, BFS uses a queue and can use more memory but visits nodes level-wise which is useful for shortest path or level-based problems

Edge Cases

Empty tree (root is NULL)

Function returns immediately without printing anything

DSA C

if (root == NULL) return; // handle empty tree

Tree with only root node

Prints the root node value only

DSA C

if (curr->left != NULL) enqueue(&q, curr->left); // enqueue left child

Tree with nodes having only one child

Only existing children are enqueued and printed correctly

DSA C

if (curr->right != NULL) enqueue(&q, curr->right); // enqueue right child

When to Use This Pattern

When a problem asks to visit nodes level by level or find shortest path in a tree, use level order BFS with a queue to process nodes in order of their depth.

Common Mistakes

Mistake: Forgetting to enqueue children nodes after visiting a node
Fix: Always enqueue left and right children if they exist after dequeuing a node

Mistake: Using recursion instead of a queue for level order traversal
Fix: Use a queue data structure to maintain the order of nodes by level

Summary

It visits all nodes in a tree level by level from top to bottom.

Use it when you need to process nodes in order of their depth or find shortest paths in trees.

The key insight is to use a queue to hold nodes of the current level before moving to the next.

Practice

1. What does the Level Order Traversal (BFS) of a binary tree do?

easy

A. Visits nodes in preorder (root, left, right)

B. Visits nodes level by level from top to bottom, left to right

C. Visits nodes in inorder (left, root, right)

D. Visits nodes in postorder (left, right, root)

Solution

1. Step 1: Understand BFS traversal

   Level Order Traversal visits nodes level by level, starting from the root and moving down each level from left to right.

2. Step 2: Compare with other traversals

   Preorder, inorder, and postorder are depth-first traversals, not level order.

3. Final Answer:

   Visits nodes level by level from top to bottom, left to right -> Option B

4. Quick Check:

   Level Order = BFS = top to bottom, left to right [OK]

Hint: Level order means visit nodes by levels, not depth [OK]

Common Mistakes:

• Confusing BFS with preorder traversal
• Thinking BFS visits nodes depth-first
• Mixing up traversal orders

2. Which of the following is the correct way to initialize a queue for BFS in C?

easy

A. struct Queue q; initializeQueue(&q); // Using struct and init function

B. queue<int> q; // C++ style, not C

C. int q[]; // array declaration without size

D. Queue q = new Queue(); // Java style, not C

Solution

1. Step 1: Identify correct C syntax for queue

   C uses structs and functions to create and initialize queues, not C++ or Java syntax.

2. Step 2: Analyze options

   struct Queue q; initializeQueue(&q); // Using struct and init function shows struct usage with an initialization function, which is correct in C. Others use C++ or Java syntax or invalid declarations.

3. Final Answer:

   struct Queue q; initializeQueue(&q); // Using struct and init function -> Option A

4. Quick Check:

   C queue needs struct + init function [OK]

Hint: Use struct and init function for queue in C [OK]

Common Mistakes:

• Using C++ or Java syntax in C code
• Declaring arrays without size
• Not initializing the queue properly

3. Given the binary tree:

    1
   / \
  2   3
 / \
4   5

What is the output of the level order traversal (BFS)?

medium

A. [1, 2, 3, 4, 5]

B. [1, 3, 2, 4, 5]

C. [4, 5, 2, 3, 1]

D. [2, 4, 5, 1, 3]

Solution

1. Step 1: Start from root and enqueue nodes level-wise

   Start with root 1, then enqueue its children 2 and 3.

2. Step 2: Visit nodes in queue order

   Visit 1, then 2 and 3, then children of 2 which are 4 and 5.

3. Final Answer:

   [1, 2, 3, 4, 5] -> Option A

4. Quick Check:

   Level order visits nodes by levels: 1, then 2 & 3, then 4 & 5 [OK]

Hint: Visit nodes level by level, left to right [OK]

Common Mistakes:

• Swapping order of children
• Confusing BFS with DFS orders
• Listing nodes in reverse order

4. Consider this C code snippet for level order traversal:

void levelOrder(struct Node* root) {
    if (!root) return;
    struct Queue q;
    initQueue(&q);
    enqueue(&q, root);
    while (!isEmpty(&q)) {
        struct Node* curr = dequeue(&q);
        printf("%d ", curr->data);
        if (curr->left) enqueue(&q, curr->left);
        if (curr->right) enqueue(&q, curr->right);
    }
}

What is the likely bug if the output is empty?

medium

A. The printf statement is missing a newline

B. The enqueue function does not add nodes correctly

C. The root node is NULL

D. Queue is not initialized properly before use

Solution

1. Step 1: Check the early return condition

   The function has if (!root) return; which skips all printing if root is NULL, leading to empty output.

2. Step 2: Verify other possibilities

   Queue is initialized properly with initQueue(&q); printf missing newline wouldn't cause empty output; enqueue issues are possible but less direct than NULL root.

3. Final Answer:

   The root node is NULL -> Option C

4. Quick Check:

   if (!root) return; causes empty output [OK]

Hint: Check if root is NULL before traversal [OK]

Common Mistakes:

• Overlooking the NULL root check
• Assuming the tree always has a valid root
• Focusing on queue when init is present

5. You want to print the level order traversal of a binary tree but separate each level on a new line. Which modification is needed in the BFS algorithm?

hard

A. Use recursion to print nodes level by level

B. Use two stacks instead of a queue

C. Perform inorder traversal and print newline after each node

D. Use a queue and track the number of nodes at current level to print newline after each level

Solution

1. Step 1: Understand level separation in BFS

   To print each level on a new line, track how many nodes are in the current level before processing them.

2. Step 2: Implement counting nodes per level

   Use the queue size at start of each level to know how many nodes to print before printing a newline.

3. Step 3: Analyze other options

   Two stacks are for DFS variants, inorder traversal is not level order, recursion for level order is inefficient and complex.

4. Final Answer:

   Use a queue and track the number of nodes at current level to print newline after each level -> Option D

5. Quick Check:

   Count nodes per level in queue to print newlines [OK]

Hint: Count nodes in queue per level to print newlines [OK]

Common Mistakes:

• Using stacks instead of queue for BFS
• Confusing inorder with level order
• Trying recursion for level order printing