Binary Tree Level Order Traversal

What does it solve?

Return a tree's values grouped by depth: [[root],[level 1],[level 2],…]. It's plain BFS with one extra move that separates the levels cleanly.

Key insight: before processing a level, record the current queue size = the number of nodes on that level. Dequeue exactly that many, collect their values into one list, and enqueue all their children (who form the next level). Because a FIFO queue keeps level order, that count is the clean boundary between levels → O(N).

The core idea

q = [root]
while q not empty:
  sz = len(q) # nodes on this level
  level = []
  for _ in range(sz):
    n = q.popleft(); level.append(n.val)
    push n.left, n.right if present
  result.append(level)

Complexity

Time complexity

O(N)

Each node is enqueued and dequeued exactly once, and its children are pushed once.

Space complexity

O(N)

The queue can hold a full level, which for a balanced tree is up to N/2 nodes at the widest.

Examples & edge cases

Live animation — snapshot level size, drain, collect

visiting (dequeued) in queue done level boundary

Binary tree (dashed band = current level)

Queue (FIFO)

empty

Result — one list per level

none yet

Current step detail

visiting = — queue = — level = — levels = —

Step — of —

visiting node

—

dequeued

queue size

—

waiting

level index

—

current depth

nodes done

—

of total

Select an example and press Play to start.

✓ Done

SpeedMedium

Step-by-step table

Step	phase	node	level	enqueued	queue size	result

C++ implementation

level_order.cpp

#include <bits/stdc++.h>
using namespace std;
struct TreeNode { int val; TreeNode *left, *right; };

// Level order: group values by depth (LeetCode 102)
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;

    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();          // snapshot this level's node count
        vector<int> level;
        for (int i = 0; i < sz; i++) {
            TreeNode* n = q.front(); q.pop();
            level.push_back(n->val);
            if (n->left)  q.push(n->left);   // children = next level
            if (n->right) q.push(n->right);
        }
        res.push_back(level);
    }
    return res;
}

My Notes

📝Notes✅

▼

●Start typing to save...0 chars

Practice this problem