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.

Practice

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

easy

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

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

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

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

Solution

1. Step 1: Understand Level Order Traversal

   Level order traversal visits nodes level by level starting from the root, moving left to right on each level.

2. Step 2: Compare with other traversals

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

3. Final Answer:

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

4. Quick Check:

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

Hint: Level order means visiting nodes level by level [OK]

Common Mistakes:

• Confusing level order with preorder traversal
• Thinking level order is depth-first
• Mixing up traversal orders

2. Which of the following is the correct C++ syntax to declare a queue of TreeNode pointers for BFS?

easy

A. queue<TreeNode> q;

B. queue q;

C. queue q;

D. queue q;

Solution

1. Step 1: Understand queue declaration for pointers

   We need a queue that stores pointers to TreeNode objects, so use queue.

2. Step 2: Check other options

   queue<TreeNode> stores objects, not pointers; queue is invalid syntax; queue is invalid for queue.

3. Final Answer:

   queue q; -> Option B

4. Quick Check:

   Queue of pointers = queue [OK]

Hint: Use * for pointer types in queue declaration [OK]

Common Mistakes:

• Using queue<TreeNode> instead of queue
• Trying to use references in queue declaration
• Incorrect syntax with array brackets

3. What is the output of the following code snippet performing level order traversal on this tree?

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Tree structure:
//     1
//    / \
//   2   3
//  /   / \
// 4   5   6

TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->right->left = new TreeNode(5);
root->right->right = new TreeNode(6);

queue q;
q.push(root);
while (!q.empty()) {
  TreeNode* node = q.front(); q.pop();
  cout << node->val << " ";
  if (node->left) q.push(node->left);
  if (node->right) q.push(node->right);
}

medium

A. 2 4 1 3 5 6

B. 1 3 2 6 5 4

C. 4 2 5 3 6 1

D. 1 2 3 4 5 6

Solution

1. Step 1: Trace the queue operations

   Start with root (1). Queue: [1]. Output: "". Pop 1, output "1 ". Push 2 and 3. Queue: [2,3]. Pop 2, output "2 ". Push 4. Queue: [3,4]. Pop 3, output "3 ". Push 5 and 6. Queue: [4,5,6]. Pop 4, output "4 ". No children. Queue: [5,6]. Pop 5, output "5 ". No children. Queue: [6]. Pop 6, output "6 ". No children. Queue empty.

2. Step 2: Combine outputs

   Concatenate outputs: 1 2 3 4 5 6

3. Final Answer:

   1 2 3 4 5 6 -> Option D

4. Quick Check:

   Level order traversal output = 1 2 3 4 5 6 [OK]

Hint: Follow queue push/pop order to get output [OK]

Common Mistakes:

• Mixing left and right child order
• Confusing preorder with level order output
• Forgetting to push children in correct order

4. Identify the bug in this level order traversal code snippet and select the fix:

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

medium

A. Missing q.pop() inside the while loop

B. Should use stack instead of queue

C. Need to check if root is nullptr before pushing

D. cout statement should be after popping

Solution

1. Step 1: Analyze the while loop

   The code pushes root, then loops while queue not empty. It gets front node but never removes it with q.pop(), causing infinite loop.

2. Step 2: Identify fix

   Adding q.pop() after processing node removes it from queue, allowing loop to progress.

3. Final Answer:

   Missing q.pop() inside the while loop -> Option A

4. Quick Check:

   Queue pop missing causes infinite loop [OK]

Hint: Always pop after processing front in BFS loop [OK]

Common Mistakes:

• Forgetting to pop queue front
• Using stack instead of queue for BFS
• Not checking for nullptr root before pushing

5. Given a binary tree, how can you modify the level order traversal to return a vector of vectors, where each inner vector contains nodes at that level? Which approach is correct?

vector levelOrder(TreeNode* root) {
  vector result;
  if (!root) return result;
  queue q;
  q.push(root);
  while (!q.empty()) {
    int size = q.size();
    vector<int> level;
    for (int i = 0; i < size; i++) {
      TreeNode* node = q.front(); q.pop();
      level.push_back(node->val);
      if (node->left) q.push(node->left);
      if (node->right) q.push(node->right);
    }
    result.push_back(level);
  }
  return result;
}

hard

A. Use recursion to collect nodes at each depth

B. Push all nodes into a stack and pop by levels

C. Use a loop over current queue size to separate levels

D. Traverse tree inorder and group nodes by value

Solution

1. Step 1: Understand level grouping in BFS

   Using the queue size at each iteration lets us process all nodes at the current level before moving to the next.

2. Step 2: Evaluate other options

   Stack is LIFO, not suitable for level order. Recursion can do level grouping but is not BFS. Inorder traversal does not group by levels.

3. Final Answer:

   Use a loop over current queue size to separate levels -> Option C

4. Quick Check:

   Queue size loop separates levels in BFS [OK]

Hint: Use queue size to process one level at a time [OK]

Common Mistakes:

• Using stack instead of queue for level order
• Trying inorder traversal for level grouping
• Ignoring queue size to separate levels