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++

#include <iostream>
#include <queue>
using namespace std;

struct Node {
  int val;
  Node* left;
  Node* right;
};

void levelOrder(Node* root) {
  if (!root) return;
  queue<Node*> q;
  q.push(root);
  while (!q.empty()) {
    Node* curr = q.front(); q.pop();
    cout << curr->val << " ";
    if (curr->left) q.push(curr->left);
    if (curr->right) q.push(curr->right);
  }
}

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

Execution Table

Step	Operation	Nodes in Queue	Pointer Changes	Visual State
1	Start: Add root (1) to queue	[1]	queue: push(1)	Tree: 1 / \ 2 3
2	Pop front (1), visit node	[ ]	queue: pop(1)	Visited: 1 Queue: []
3	Add left child (2) to queue	[2]	queue: push(2)	Queue: [2]
4	Add right child (3) to queue	[2,3]	queue: push(3)	Queue: [2,3]
5	Pop front (2), visit node	[3]	queue: pop(2)	Visited: 1,2 Queue: [3]
6	Add left child (4) to queue	[3,4]	queue: push(4)	Queue: [3,4]
7	Add right child (5) to queue	[3,4,5]	queue: push(5)	Queue: [3,4,5]
8	Pop front (3), visit node	[4,5]	queue: pop(3)	Visited: 1,2,3 Queue: [4,5]
9	No children to add	[4,5]	none	Queue: [4,5]
10	Pop front (4), visit node	[5]	queue: pop(4)	Visited: 1,2,3,4 Queue: [5]
11	No children to add	[5]	none	Queue: [5]
12	Pop front (5), visit node	[]	queue: pop(5)	Visited: 1,2,3,4,5 Queue: []
13	No children to add	[]	none	Queue empty, traversal done

💡 Queue is empty, all nodes visited in level order

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	Final
queue	[]	[1]	[]	[2]	[2,3]	[3]	[3,4]	[3,4,5]	[4,5]	[4,5]	[5]	[5]	[]
visited_nodes	[]	[1]	[1]	[1,2]	[1,2]	[1,2,3]	[1,2,3]	[1,2,3]	[1,2,3,4]	[1,2,3,4]	[1,2,3,4,5]	[1,2,3,4,5]	[1,2,3,4,5]

Key Moments - 3 Insights

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

Because we want to visit nodes level by level. Adding children after visiting ensures nodes on the current level are processed before moving deeper. See steps 3,4 and 6,7 in execution_table.

Why does the loop stop when the queue is empty?

The queue holds nodes to visit. When empty, no nodes remain to process, so traversal is complete. See step 13 in execution_table where queue is empty.

Why do we pop the front node from the queue before visiting it?

Popping front removes the node from the queue so we don't visit it again and keeps the queue updated. See steps 2,5,8,10,12 where pop happens before visit.

Visual Quiz - 3 Questions

Look at the execution_table, what nodes are in the queue after step 7?

A [3,4,5]

B [4,5]

C [2,3]

D [5]

💡 Hint

Check the 'Nodes in Queue' column at step 7 in execution_table.

At which step does the queue become empty?

A Step 12

B Step 10

C Step 13

D Step 9

💡 Hint

Look for the step where 'Nodes in Queue' is empty in execution_table.

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

A Queue would have the root node again

B Queue would be empty

C Queue would have null nodes

D Queue would have left and right children

💡 Hint

Refer to steps 3 and 4 where children are added only if they exist.

Concept Snapshot

Level Order BFS visits tree nodes level by level.
Use a queue to hold nodes to visit.
Start by adding root to queue.
Loop: pop front, visit, add children.
Stop when queue is empty.
Print nodes in order visited.

Full Transcript

Level Order BFS traversal visits nodes of a binary tree level by level from top to bottom. We start by adding the root node to a queue. Then, while the queue is not empty, we remove the front node, visit it (process its value), and add its left and right children to the queue if they exist. This process continues until the queue is empty, meaning all nodes have been visited in level order. The execution table shows each step with the queue state and visited nodes. Key moments clarify why children are added after visiting and why the loop stops when the queue is empty. The visual quiz tests understanding of queue contents and stopping condition. This method ensures nodes are visited breadth-first, level by level.