Tree Traversal Level Order BFS in DSA C++

Mental Model

Visit tree nodes level by level from top to bottom, left to right, like reading lines in a book.

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

      1
     / \
    2   3
   / \   \
  4   5   6

Queue: [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 child of 3

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

Step 1: Start with root node 1 in queue

Queue: [1] ↑

Why: We begin traversal from the root

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

Printed: 1
Queue: [2, 3] ↑

Why: Visit current node and prepare to visit next level

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

Printed: 1 2
Queue: [3, 4, 5] ↑

Why: Continue level order by visiting next node in queue

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

Printed: 1 2 3
Queue: [4, 5, 6] ↑

Why: Visit all nodes at current level before moving deeper

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

Printed: 1 2 3 4
Queue: [5, 6] ↑

Why: Leaf nodes have no children to add

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

Printed: 1 2 3 4 5
Queue: [6] ↑

Why: Continue visiting remaining nodes

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

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

Why: Traversal complete when queue is empty

Result:

1 2 3 4 5 6

Annotated Code

DSA C++

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

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

void levelOrderTraversal(TreeNode* root) {
    if (!root) return; // handle empty tree
    queue<TreeNode*> q;
    q.push(root); // start with root
    while (!q.empty()) {
        TreeNode* curr = q.front();
        q.pop(); // remove current node
        cout << curr->val << " "; // print current node
        if (curr->left) q.push(curr->left); // add left child
        if (curr->right) q.push(curr->right); // add right child
    }
}

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

    levelOrderTraversal(root);
    return 0;
}

if (!root) return; // handle empty tree

stop if tree is empty

q.push(root); // start with root

initialize queue with root node

TreeNode* curr = q.front(); q.pop(); // remove current node

take next node from queue to visit

cout << curr->val << " "; // print current node

output current node value

if (curr->left) q.push(curr->left); // add left child

enqueue left child if exists

if (curr->right) q.push(curr->right); // add right child

enqueue right child if exists

Output

1 2 3 4 5 6 

Complexity Analysis

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

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

vs Alternative: Compared to depth-first traversals, BFS uses more memory but visits nodes level-wise which is useful for shortest path or level info

Edge Cases

Empty tree

Function returns immediately without printing

DSA C++

if (!root) return; // handle empty tree

Tree with only root node

Prints root value only

DSA C++

if (!root) return; // handle empty tree

Tree with missing children

Only existing children are added to queue, no errors

DSA C++

if (curr->left) q.push(curr->left); // add left 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 because it processes nodes in layers.

Common Mistakes

Mistake: Forgetting to check if left or right child exists before adding to queue
Fix: Add condition checks before pushing children to queue

Mistake: Using recursion which leads to depth-first traversal instead of BFS
Fix: Use a queue and iterative approach to ensure level order

Summary

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

Use when you need to process nodes in order of their distance from the root.

The key is to use a queue to keep track of nodes at the current level before moving deeper.

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