Level-order traversal (BFS) in Data Structures Theory - Step-by-Step Execution

Concept Flow - Level-order traversal (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 until all nodes are visited.

Execution Sample

Data Structures Theory

queue = [root]
while queue:
  node = queue.pop(0)
  visit(node)
  if node.left: queue.append(node.left)
  if node.right: queue.append(node.right)

This code visits nodes in a tree level by level using a queue.

Analysis Table

Step	Operation	Queue Before	Node Visited	Queue After	Visual State
1	Start	[]	None	[A]	Queue initialized with root A
2	Dequeue	[A]	A	[]	Visit A, queue empty after dequeue
3	Enqueue children	[]	A	[B, C]	Add B and C to queue
4	Dequeue	[B, C]	B	[C]	Visit B, queue has C
5	Enqueue children	[C]	B	[C, D, E]	Add D and E to queue
6	Dequeue	[C, D, E]	C	[D, E]	Visit C, queue has D and E
7	Enqueue children	[D, E]	C	[D, E, F]	Add F to queue
8	Dequeue	[D, E, F]	D	[E, F]	Visit D, queue has E and F
9	Enqueue children	[E, F]	D	[E, F]	D has no children
10	Dequeue	[E, F]	E	[F]	Visit E, queue has F
11	Enqueue children	[F]	E	[F]	E has no children
12	Dequeue	[F]	F	[]	Visit F, queue empty
13	Enqueue children	[]	F	[]	F has no children
14	End	[]	None	[]	Queue empty, traversal complete

💡 Queue becomes empty after visiting all nodes, traversal ends.

State Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	After Step 9	After Step 12	Final
queue	[]	[A]	[B, C]	[C, D, E]	[D, E, F]	[E, F]	[]	[]
node_visited	None	A	B	C	D	E	F	None

Key Insights - 3 Insights

Why do we use a queue instead of a stack for level-order traversal?

Because a queue processes nodes in the order they are added (FIFO), ensuring nodes are visited level by level. Using a stack (LIFO) would visit nodes depth-first, not level-order. See execution_table steps 2-3 and 4-5 where children are enqueued and visited in order.

What happens if a node has no children?

No new nodes are added to the queue for that node. The queue size decreases by one after visiting that node. See steps 9 and 11 where nodes D and E have no children, so the queue remains unchanged except for the removal of the visited node.

How do we know when the traversal is complete?

When the queue becomes empty, meaning there are no more nodes to visit. This is shown in step 14 where the queue is empty and traversal ends.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what nodes are in the queue after enqueuing children of B?

A [D, E, C]

B [C, D, E]

C [B, C, D, E]

D [C, B, D, E]

💡 Hint

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

At which step does the queue become empty, signaling traversal completion?

A Step 12

B Step 10

C Step 14

D Step 9

💡 Hint

Look at the 'Queue After' column and the exit_note.

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

A Queue would be [D, E]

B Queue would be [D, E, F]

C Queue would be [E, F]

D Queue would be [C, D, E]

💡 Hint

Refer to step 7 where children of C are enqueued; if none, no new nodes added.

Concept Snapshot

Level-order traversal visits tree nodes level by level.
Use a queue to hold nodes to visit.
Start by enqueueing root.
While queue not empty: dequeue node, visit it, enqueue its children.
Traversal ends when queue is empty.

Full Transcript

Level-order traversal, also called Breadth-First Search (BFS), visits nodes in a tree one level at a time from top to bottom. It uses a queue to keep track of nodes to visit next. Starting with the root node, it adds children of each visited node to the queue. This process continues until the queue is empty, meaning all nodes have been visited. The execution table shows each step: nodes are dequeued, visited, and their children enqueued. Key points include why a queue is used (to maintain order), what happens when nodes have no children (no additions to queue), and how traversal ends (empty queue). This method ensures nodes are visited in order of their distance from the root.

Practice

1. What is the main data structure used in level-order traversal (BFS) of a binary tree?

easy

A. Linked List

B. Stack

C. Queue

D. Hash Table

Solution

1. Step 1: Understand traversal method

   Level-order traversal visits nodes level by level, which requires processing nodes in the order they appear.

2. Step 2: Identify suitable data structure

   A queue follows First-In-First-Out (FIFO) order, perfect for visiting nodes level by level.

3. Final Answer:

   Queue -> Option C

4. Quick Check:

   Level-order traversal uses a queue [OK]

Hint: Level-order uses FIFO structure: queue [OK]

Common Mistakes:

• Confusing queue with stack (LIFO)
• Thinking hash table stores order
• Assuming linked list is used directly

2. Which of the following is the correct syntax to enqueue a node n into a queue named q in Python during level-order traversal?

easy

A. q.append(n)

B. q.enqueue(n)

C. q.push(n)

D. q.insert(n)

Solution

1. Step 1: Identify Python queue implementation

   In Python, a list can be used as a queue where append() adds elements to the end.

2. Step 2: Confirm enqueue operation

   Using q.append(n) correctly adds node n to the queue's rear.

3. Final Answer:

   q.append(n) -> Option A

4. Quick Check:

   Python queue enqueue uses append() [OK]

Hint: Use append() to add nodes to Python queue [OK]

Common Mistakes:

• Using push() which is not a Python list method
• Using enqueue() which is not built-in
• Using insert() which adds at wrong position

3. Given the binary tree:

    1
   / \
  2   3
 /   / \
4   5   6

What is the output of a level-order traversal?

medium

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

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

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

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

Solution

1. Step 1: Traverse level by level

   Start at root: 1. Then next level: 2 and 3. Then next level: 4, 5, 6.

2. Step 2: List nodes in visiting order

   Collect nodes as visited: [1, 2, 3, 4, 5, 6].

3. Final Answer:

   [1, 2, 3, 4, 5, 6] -> Option B

4. Quick Check:

   Level-order visits nodes top to bottom, left to right [OK]

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

Common Mistakes:

• Mixing order of nodes in same level
• Listing nodes in depth-first order
• Reversing levels incorrectly

4. Consider this Python snippet for level-order traversal:

queue = [root]
while queue:
    node = queue.pop()
    print(node.value)
    if node.left:
        queue.append(node.left)
    if node.right:
        queue.append(node.right)

What is the main error in this code?

medium

A. Using pop() removes last element, not first

B. Appending children before popping node

C. Not checking if node is null

D. Printing node value before adding children

Solution

1. Step 1: Understand queue behavior

   Level-order traversal requires FIFO order, so nodes must be removed from the front.

2. Step 2: Identify pop() behavior

   pop() without index removes last element (LIFO), causing incorrect traversal order.

3. Final Answer:

   Using pop() removes last element, not first -> Option A

4. Quick Check:

   pop() removes from end, use pop(0) for queue [OK]

Hint: Use pop(0) to dequeue from front in Python list [OK]

Common Mistakes:

• Using pop() instead of pop(0)
• Ignoring queue order importance
• Assuming append order fixes pop issue

5. You want to find the shortest path from the root to a target node in a binary tree using level-order traversal. Which modification ensures you stop traversal as soon as the target is found?

hard

A. Continue traversal until queue is empty, then check target

B. Traverse only left children until target is found

C. Add all nodes to a stack and pop until target is found

D. Check each node during dequeue; stop and return path if target found

Solution

1. Step 1: Understand BFS for shortest path

   BFS visits nodes level by level, so the first time target is found is the shortest path.

2. Step 2: Implement early stopping

   Check each node when dequeued; if it matches target, stop traversal immediately and return path.

3. Final Answer:

   Check each node during dequeue; stop and return path if target found -> Option D

4. Quick Check:

   Stop BFS on target found for shortest path [OK]

Hint: Stop BFS immediately when target node is dequeued [OK]

Common Mistakes:

• Traversing entire tree unnecessarily
• Using stack instead of queue for shortest path
• Ignoring right children in traversal