Tree Traversal Level Order BFS in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Level Order Traversal on a Simple Binary Tree

What is the output of the following C++ code performing level order traversal (BFS) on the given binary tree?

DSA C++

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

#include <iostream>
#include <queue>
#include <vector>

std::vector<int> levelOrder(Node* root) {
    std::vector<int> result;
    if (!root) return result;
    std::queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* node = q.front();
        q.pop();
        result.push_back(node->val);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return result;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    std::vector<int> output = levelOrder(root);
    for (int v : output) std::cout << v << " ";
    return 0;
}

A 2 3 1 4 5

B 1 3 2 5 4

C 4 5 2 3 1

D 1 2 3 4 5

💡 Hint

Remember, level order traversal visits nodes level by level from left to right.

The code uses a queue to visit nodes level by level. Starting from root (1), then its children (2, 3), then their children (4, 5). So output is 1 2 3 4 5.

🧠 Conceptual

intermediate

Number of Levels in Level Order Traversal

Given a binary tree, how many levels will the level order traversal visit for the tree below? Tree structure: - Root node 10 - Left child 20 - Right child 30 - Left child of 20 is 40 - Right child of 20 is 50 - Left child of 30 is 60

A 5

B 3

C 4

D 2

💡 Hint

Count the levels from root down to the deepest leaf.

The tree has root level (10), second level (20, 30), and third level (40, 50, 60). So total 3 levels.

🔧 Debug

advanced

Identify the Bug in Level Order Traversal Code

What error will the following C++ code produce when performing level order traversal?

DSA C++

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

#include <iostream>
#include <queue>
#include <vector>

std::vector<int> levelOrder(Node* root) {
    std::vector<int> result;
    std::queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* node = q.front();
        q.pop();
        result.push_back(node->val);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return result;
}

int main() {
    Node* root = nullptr;
    std::vector<int> output = levelOrder(root);
    for (int v : output) std::cout << v << " ";
    return 0;
}

A Segmentation fault (runtime error)

B Empty output (no values printed)

C Compilation error due to missing header

D Infinite loop

💡 Hint

Check what happens when root is nullptr but still pushed into the queue.

The code pushes nullptr into the queue without checking if root is null. Then accessing node->val causes segmentation fault.

📝 Syntax

advanced

Syntax Error in Level Order Traversal Code

Which option contains the correct syntax to push children nodes into the queue during level order traversal?

DSA C++

if (node->left) q.push(node->left);
if (node->right) q.push(node->right);

A if node->left { q.push(node->left); } if node->right { q.push(node->right); }

B if node->left q.push(node->left); if node->right q.push(node->right);

C if (node->left) q.push(node->left); if (node->right) q.push(node->right);

D if (node->left) { q.push(node->left); } if (node->right) { q.push(node->right); }

💡 Hint

Remember C++ requires parentheses around conditions and semicolons after statements.

Option C uses correct C++ syntax with parentheses and semicolons. Others miss parentheses or semicolons causing syntax errors.

🚀 Application

expert

Level Order Traversal Output After Node Insertions

Given an initially empty binary tree, nodes are inserted in this order: 1. Insert 10 as root 2. Insert 20 as left child of 10 3. Insert 30 as right child of 10 4. Insert 40 as left child of 20 5. Insert 50 as right child of 20 6. Insert 60 as left child of 30 What is the output of the level order traversal after all insertions?

A 10 20 30 40 50 60

B 20 10 30 40 50 60

C 40 50 60 20 30 10

D 10 30 20 60 50 40

💡 Hint

Level order visits nodes level by level from left to right.

The tree levels are: Level 1: 10 Level 2: 20, 30 Level 3: 40, 50, 60 So output is 10 20 30 40 50 60.

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