DSA Pattern: BFS Level-Order Traversal

Level Order Traversal is the standard Breadth-First Search (BFS) algorithm for binary trees, processing nodes level by level.

The Queue Mechanism

We use a Queue to keep track of nodes. For each level, we find the current queue size and process exactly that many nodes, adding their children to the queue for the next level.

vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};
    vector<vector<int>> res;
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int sz = q.size();
        vector<int> level;
        for (int i = 0; i < sz; 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);
        }
        res.push_back(level);
    }
    return res;
}

Complexity: Time O(N) to visit every node. Space O(W) where W is the maximum width of the tree.