Binary Tree Level Order Traversal — Editorial

Opening the reading…

Intuitionthe queue contains the frontier of one depth at a time

The required output groups values by depth, so the traversal must finish every node at depth d before recording any node at depth d + 1. A queue gives exactly that behavior: nodes leave in the order they entered, and children are added after their parents. Because each parent adds its left child before its right child, the next depth also leaves from left to right.

The important detail is knowing where one level ends. At the beginning of a level, the queue contains exactly the nodes at that depth. Save its current size, remove exactly that many nodes, and add their children to the queue. Those new children wait for the next outer iteration, so the result receives one complete inner list per depth.

Approachone queue pass, with the level boundary made explicit

Create an empty result and return it immediately when root is null, because an empty tree has no levels and must not place a dummy empty level in the output.

Push root into a queue, because the queue's front will always be the next node to visit in breadth-first, left-to-right order.

While the queue is not empty, save its current size as the number of nodes in the next level; without this snapshot, children appended during the loop would be mistaken for part of the current level.

Create an empty level list and remove exactly the saved number of nodes, because each removal belongs to the same depth and must be grouped together.

Append each removed node's value to level, then enqueue its left child followed by its right child when they exist; this preserves the required ordering for the following depth.

Append the completed level to result only after all nodes counted by the snapshot have been processed, because the queue now represents the next frontier rather than the level just recorded.

Return result after the queue is empty, since every reachable node has then been assigned to exactly one depth list.

Complexityevery node enters and leaves the queue once

MEASURE	BOUND	WHY
Time	O(n)	Each node is enqueued once, dequeued once, and has its value appended once. The left and right child checks are constant work per node, so no node or edge is examined more than a constant number of times.
Space	O(n) extra	The output lists are required output and are excluded from the extra-space bound. The queue can hold a whole level, whose width is at most n; the temporary level list is part of the output. The worst shape for working space is a broad tree with O(n) nodes on one level.

Here n is the number of nodes in the tree and h is its height, measured in levels.

Annotated solutionC++ · iterative breadth-first search · one saved size separates levels

CPPBreadth-first traversal that snapshots the current queue size before processing a level.

#include <queue>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) {
            return result;
        }

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int size = static_cast<int>(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 != nullptr) {
                    q.push(node->left);
                }
                if (node->right != nullptr) {
                    q.push(node->right);
                }
            }

            result.push_back(level);
        }

        return result;
    }
};

The line int size = q.size() is the boundary between the two concepts in this solution: the queue itself changes during the level, but size does not. The for loop therefore processes the old frontier only. Child pointers are enqueued before the next outer iteration, and left is enqueued before right so their removal order matches the problem's left-to-right requirement.

The recursive alternativea different arrangement, useful when depth is already part of the logic

You can also perform a depth-first traversal and use the current depth to choose the result list. When a node is first visited at depth d, create result[d] if necessary and append the value there. Recursing left before right preserves the same order within each list, even though the traversal itself goes deep before visiting later nodes.

CPPDepth-first alternative that places each value into the list for its depth.

#include <vector>

using namespace std;

class Solution {
    void walk(TreeNode* node, int depth, vector<vector<int>>& result) {
        if (node == nullptr) {
            return;
        }

        if (depth == static_cast<int>(result.size())) {
            result.push_back({});
        }

        result[depth].push_back(node->val);
        walk(node->left, depth + 1, result);
        walk(node->right, depth + 1, result);
    }

public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        walk(root, 0, result);
        return result;
    }
};

This is not a time optimisation: every node is still visited once, so time remains O(n). It trades the explicit queue for the recursive call stack. The extra space is O(h), where h is the tree height, in addition to the required output; that can be much smaller than a broad level's queue, but it grows to O(n) on a completely skewed tree and can make recursion depth a practical concern.