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.