Tree Traversal Level Order BFS in DSA C - Execution Trace

Concept Flow - Tree Traversal Level Order BFS

Start at root node

↓

Add root to queue

↓

While queue not empty

↓

Remove front node from queue

↓

Visit node (process value)

↓

Add left child to queue if exists

↓

Add right child to queue if exists

↓

Repeat loop until queue empty

↓

Traversal complete

Start from the root, use a queue to visit nodes level by level, adding children to the queue as you go.

Execution Sample

DSA C

void levelOrderTraversal(Node* root) {
    Queue q;
    initQueue(&q); // Initialize the queue before use
    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);
    }
}

This code prints the nodes of a binary tree level by level using a queue.

Execution Table

Step	Operation	Node Visited	Queue Before	Queue After	Visual State
1	Start: Add root to queue	None	[]	[1]	Tree: 1 Queue: [1]
2	Dequeue node	1	[1]	[]	Visited: 1 Queue: []
3	Enqueue left child	1	[]	[2]	Queue: [2]
4	Enqueue right child	1	[2]	[2,3]	Queue: [2,3]
5	Dequeue node	2	[2,3]	[3]	Visited: 1,2 Queue: [3]
6	Enqueue left child	2	[3]	[3,4]	Queue: [3,4]
7	Enqueue right child	2	[3,4]	[3,4,5]	Queue: [3,4,5]
8	Dequeue node	3	[3,4,5]	[4,5]	Visited: 1,2,3 Queue: [4,5]
9	No children to enqueue	3	[4,5]	[4,5]	Queue: [4,5]
10	Dequeue node	4	[4,5]	[5]	Visited: 1,2,3,4 Queue: [5]
11	No children to enqueue	4	[5]	[5]	Queue: [5]
12	Dequeue node	5	[5]	[]	Visited: 1,2,3,4,5 Queue: []
13	No children to enqueue	5	[]	[]	Queue empty, traversal done

💡 Queue is empty, all nodes visited in level order

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 5	After Step 8	After Step 12	Final
Queue	[]	[1]	[]	[3]	[4,5]	[]	[]
Visited Nodes	[]	[]	[1]	[1,2]	[1,2,3]	[1,2,3,4,5]	[1,2,3,4,5]
Current Node	None	None	1	2	3	5	None

Key Moments - 3 Insights

Why do we add children to the queue after visiting the current node?

Because the queue ensures nodes are visited level by level. Adding children after visiting keeps the order correct, as shown in steps 3,4,6,7 where children are enqueued after visiting the parent (step 2,5).

What happens when the queue becomes empty?

When the queue is empty (step 13), it means all nodes have been visited. The loop stops, ending the traversal as shown in the exit note.

Why do we visit nodes in the order 1,2,3,4,5?

Because the queue processes nodes in FIFO order. Nodes are visited level by level from left to right, as seen in the visual state column and the visited nodes tracker.

Visual Quiz - 3 Questions

Look at the execution table, what is the queue state after step 4?

A [1]

B [3]

C [2,3]

D []

💡 Hint

Check the 'Queue After' column in row for step 4.

At which step does the node with value 3 get dequeued?

A Step 8

B Step 10

C Step 5

D Step 12

💡 Hint

Look at the 'Node Visited' column to find when 3 is dequeued.

If the node 2 had no children, how would the queue after step 7 change?

A [3,4,5]

B [3]

C [3,5]

D [4,5]

💡 Hint

Refer to step 7 where children of node 2 are enqueued; removing them changes the queue.

Concept Snapshot

Level Order Traversal (BFS) visits nodes level by level.
Use a queue to hold nodes to visit.
Start by enqueueing root.
Dequeue node, visit it, enqueue its children.
Repeat until queue empty.
Result: nodes visited in breadth-first order.

Full Transcript

Level Order Traversal uses a queue to visit tree nodes level by level. We start by adding the root node to the queue. Then, while the queue is not empty, we remove the front node, visit it, and add its left and right children to the queue if they exist. This process continues until all nodes are visited and the queue is empty. The order of visiting nodes is breadth-first, meaning all nodes at one level are visited before moving to the next level. The execution table shows each step, the queue state before and after, and the nodes visited. The variable tracker follows the queue and visited nodes over time. Key moments clarify why children are added after visiting and what happens when the queue empties. The visual quiz tests understanding of queue states and node visitation order. This method ensures a complete and level-wise traversal of the tree.

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