L8: Level Order Traversal of Binary Tree | BFS | C++ | Java

Level Order Traversal is a fundamental tree traversal technique that visits every node level by level, starting from the root and moving downwards from left to right. This approach forms the basis of Breadth-First Search (BFS) in tree and graph data structures.

1. Why Do We Need Level Order Traversal?

Traditional depth-first traversals (such as Inorder, Preorder, and Postorder) explore a tree vertically, diving deep into branches before exploring siblings. However, many real-world applications require processing data in horizontal layers:

• Organizational charts: Printing employees tier by tier from top management down to entry-level staff.
• UI rendering & DOM parsing: Evaluating layout hierarchies level by level.
• Shortest path problems: In unweighted trees, BFS guarantees finding the shortest path to any node.

2. Core Mental Model & Analogy

Real-Life Analogy: The Reception Line

Imagine a manager inspecting a multi-tier corporate hierarchy standing in a courtyard:

1. The manager stands at the front gate and admits the top executive (Root).
2. The executive steps forward, looks to their left and right, and calls out their direct subordinates, who line up in an orderly queue behind them.
3. The manager processes each line sequentially, ensuring everyone at Level 1 is processed before anyone at Level 2 is allowed to step forward.

3. The Queue-Based Data Structure Strategy

To achieve level-by-level processing, we cannot rely solely on recursive call stacks (which perform depth-first searches). Instead, we require two primary data structures:

1. A Queue (FIFO - First In, First Out): To keep track of nodes waiting to be explored.
2. A 2D Container (vector<vector<int>> in C++ or List<List<Integer>> in Java): To group and store nodes level by level for our final answer.

4. Step-by-Step Evolution of the Algorithm

Let us trace the algorithm using a sample binary tree:

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

Step 1: Initialization

• Push the root node (1) into the queue.
• Initialize an empty answer container (vector<vector<int>>).

Step 2: Level 1 Iteration

• Queue contains: [1]
• Current size of queue = 1
• Pop 1, examine its children:
  • Left child 2 exists -> Push to queue.
  • Right child 3 exists -> Push to queue.
• Store [1] in our level vector. Answer so far: [[1]].
• Queue now contains: [2, 3]

Step 3: Level 2 Iteration

• Queue contains: [2, 3]
• Current size of queue = 2 (we process exactly 2 nodes for this level).
• Pop 2:
  • Left child 4 -> Push to queue.
  • Right child 5 -> Push to queue.
• Pop 3:
  • Left child 6 -> Push to queue.
  • Right child 7 -> Push to queue.
• Store [2, 3] in our level vector. Answer so far: [[1], [2, 3]].
• Queue now contains: [4, 5, 6, 7]

Step 4: Level 3 Iteration

• Queue contains: [4, 5, 6, 7]
• Current size of queue = 4.
• Pop 4, 5, 6, 7: None have children.
• Store [4, 5, 6, 7] in our level vector. Answer so far: [[1], [2, 3], [4, 5, 6, 7]].
• Queue is now empty. Traversal complete!

5. Complete Flow Walkthrough

6. Implementation Code (C++ & Java)

C++ Implementation

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

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == nullptr) {
            return ans;
        }
        
        queue<TreeNode*> 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();
                
                // Push left child if it exists
                if (node->left != nullptr) {
                    q.push(node->left);
                }
                // Push right child if it exists
                if (node->right != nullptr) {
                    q.push(node->right);
                }
                
                level.push_back(node->val);
            }
            ans.push_back(level);
        }
        return ans;
    }
};

Java Implementation

import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> level = new ArrayList<>();
            
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                
                // Push left child if it exists
                if (node.left != null) {
                    q.offer(node.left);
                }
                // Push right child if it exists
                if (node.right != null) {
                    q.offer(node.right);
                }
                
                level.add(node.val);
            }
            ans.add(level);
        }
        return ans;
    }
}

7. Complexity Analysis

Note: The space utilized by the output 2D array (ans) storing all nodes is technically required to return the result and is generally excluded when calculating auxiliary space complexity. However, the queue storage strictly bounds auxiliary space to $O(N)$.

Summary and Key Takeaways

• Definition: Level Order Traversal visits tree nodes tier by tier from top to bottom, left to right.
• Core Mechanism: Utilizes a Queue data structure enforcing FIFO (First In, First Out) behavior to maintain correct horizontal sequencing.
• Size Tracking: Capturing q.size() at the beginning of each level iteration is crucial to batch nodes correctly per horizontal tier.
• Child Propagation: Always check if left and right child pointers are non-null before pushing them into the queue to avoid null pointer exceptions.
• Time & Space: Both time and auxiliary space complexities evaluate to $O(N)$ for a tree with $N$ nodes.
• Foundation for BFS: Mastering level order traversal unlocks classic Breadth-First Search algorithms used in shortest path and graph problems.