Tree Traversal Level Order BFS in DSA C++ - Time & Space Complexity

Time Complexity: Tree Traversal Level Order BFS

O(n)

Understanding Time Complexity

We want to understand how long it takes to visit all nodes in a tree using level order traversal.

How does the time grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void levelOrderTraversal(TreeNode* root) {
    if (!root) return;
    std::queue q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        // process node->val
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}
    

This code visits every node in the tree level by level, from top to bottom and left to right.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each node once inside the while loop.
• How many times: Exactly once for each node in the tree.

How Execution Grows With Input

As the number of nodes grows, the number of visits grows the same way.

Input Size (n)	Approx. Operations
10	About 10 visits
100	About 100 visits
1000	About 1000 visits

Pattern observation: The operations grow directly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows linearly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "Level order traversal takes more than linear time because it uses a queue and loops inside loops."

[OK] Correct: Each node is added and removed from the queue exactly once, so the total work is proportional to the number of nodes, not more.

Interview Connect

Understanding level order traversal time helps you explain how breadth-first search works efficiently on trees and graphs.

Self-Check

"What if the tree is very unbalanced and looks like a linked list? How would the time complexity change?"

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