Tree Traversal Level Order BFS in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is Level Order Traversal in a tree?

Level Order Traversal visits nodes level by level from top to bottom and left to right within each level, like reading a book line by line.

beginner

Which data structure is commonly used to implement Level Order Traversal (BFS) in a tree?

A queue is used to keep track of nodes to visit next, ensuring nodes are processed in the order they appear level-wise.

beginner

In Level Order Traversal, what is the order of visiting nodes in this tree? 1 / \ 2 3 / \ 4 5

The nodes are visited in this order: 1 -> 2 -> 3 -> 4 -> 5

intermediate

Why does Level Order Traversal use BFS instead of DFS?

Because BFS visits nodes level by level, it naturally fits Level Order Traversal, while DFS goes deep first and does not preserve level order.

beginner

What is the time complexity of Level Order Traversal on a tree with n nodes?

The time complexity is O(n) because each node is visited exactly once.

Which data structure is essential for implementing Level Order Traversal (BFS) in a tree?

A Array

B Stack

C Hash Map

D Queue

Queue is used to process nodes in the order they appear level-wise.

What is the first node visited in Level Order Traversal of a tree?

A Root node

B Leftmost leaf

C Rightmost leaf

D Any random node

Traversal starts from the root node at the top level.

In Level Order Traversal, after visiting a node, which nodes are enqueued next?

A Its children from left to right

B Its parent node

C Its siblings

D Nodes at the last level

Children are enqueued left to right to visit them in the next level.

What is the output of Level Order Traversal for this tree? 10 / \ 20 30 / \ 40 50

A 20 -> 10 -> 30 -> 40 -> 50

B 10 -> 30 -> 20 -> 50 -> 40

C 10 -> 20 -> 30 -> 40 -> 50

D 50 -> 40 -> 30 -> 20 -> 10

Nodes are visited level by level from left to right.

What is the time complexity of Level Order Traversal on a tree with n nodes?

A O(log n)

B O(n)

C O(n^2)

D O(1)

Each node is visited once, so time complexity is linear.

Explain how Level Order Traversal (BFS) works on a binary tree.

Think about visiting nodes like reading lines in a book.

Describe the difference between Level Order Traversal and Depth First Traversal.

Compare how nodes are visited in each method.

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