Tree Traversal Level Order BFS in DSA C++ - Build from Scratch

Tree Traversal Level Order BFS

📖 Scenario: You work at a company that manages family trees. You need to show family members level by level, starting from the oldest ancestor.

🎯 Goal: Build a program that creates a simple family tree and prints the names of family members level by level using Breadth-First Search (BFS).

📋 What You'll Learn

Create a struct Node for tree nodes with string name, Node* left, and Node* right.

Create the family tree with exact names and structure.

Use a queue to perform level order traversal (BFS).

Print the names in level order separated by spaces.

💡 Why This Matters

🌍 Real World

Level order traversal is used in family trees, organizational charts, and network broadcasting to visit nodes level by level.

💼 Career

Understanding BFS and tree traversal is essential for software engineers working with hierarchical data and algorithms.

1

Create the Node struct and family tree

Create a struct Node with string name, Node* left, and Node* right. Then create the family tree with root named "Grandpa", left child "Dad", right child "Uncle", and "Dad" has left child "Me" and right child "Sister".

DSA C++

// Define struct Node
// Create nodes and link them to form the family tree

Hint

Define the Node struct with a constructor. Then create nodes and connect them as described.

2

Include queue and prepare for BFS

Include the <queue> header and create a queue<Node*> named q to help with level order traversal. Push the root node into q.

DSA C++

#include 
// Create queue q
// Push root into q
// Your code here

Hint

Remember to include <queue> and create a queue of Node*. Then push the root node into it.

3

Implement the level order traversal loop

Use a while loop that runs while q is not empty. Inside the loop, get the front node from q into Node* current, then pop it from q. Print current->name followed by a space. If current->left is not nullptr, push it into q. If current->right is not nullptr, push it into q.

DSA C++

// Use while loop with condition !q.empty()
// Inside loop: Node* current = q.front(); q.pop();
// Print current->name and a space
// If current->left != nullptr, push it to q
// If current->right != nullptr, push it to q
// Your code here

Hint

Use a queue to visit nodes level by level. Print the name and add children to the queue.

4

Print the final level order traversal output

Add a cout statement to print a newline character \n after the level order traversal loop to end the output cleanly.

DSA C++

// Print a newline after the traversal
// Your code here

Hint

After printing all names with spaces, print a newline to finish the output.

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