Level-Order Traversal (BFS): Visiting a Tree Level by Level

Level-order traversal visits a tree breadth-first — all nodes at depth 0, then all nodes at depth 1, and so on, left to right. Where DFS traversals use a stack (or recursion), level-order uses a queue: you process a node and enqueue its children, so nodes come out in the exact order they should be visited. It runs in O(n) time.

We reuse the standard TreeNode.

The idea: a queue does the work

A queue is first-in, first-out. Start by enqueueing the root. Repeatedly dequeue a node, process it, and enqueue its non-null children. Because children are always added behind the current level, every node on a level is processed before any node on the next.

        (1)
       /   \
     (2)    (3)
     / \      \
   (4) (5)    (6)

Level-order: 1 2 3 4 5 6

Flat level-order

This emits every value in breadth-first order as a single list:

std::vector<int> levelOrder(TreeNode* root) {
    std::vector<int> out;
    if (root == nullptr) return out;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        out.push_back(node->val);
        if (node->left)  q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return out;
}

List<Integer> levelOrder(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        TreeNode node = q.poll();
        out.add(node.val);
        if (node.left != null)  q.add(node.left);
        if (node.right != null) q.add(node.right);
    }
    return out;
}

function levelOrder(root) {
  const out = [];
  if (root === null) return out;
  const q = [root];
  let head = 0;
  while (head < q.length) {
    const node = q[head++];
    out.push(node.val);
    if (node.left)  q.push(node.left);
    if (node.right) q.push(node.right);
  }
  return out;
}

from collections import deque

def level_order(root):
    out = []
    if root is None:
        return out
    q = deque([root])
    while q:
        node = q.popleft()
        out.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    return out

For beginners: In JavaScript, using array.shift() to dequeue is O(n) per call. The example above uses a moving head index so each dequeue stays O(1).

Grouping by level

Often you want a list per level (e.g. for a zigzag print or a right-side view). The trick: snapshot the queue’s size at the start of each loop — that count is exactly how many nodes are on the current level.

std::vector<std::vector<int>> levelsOf(TreeNode* root) {
    std::vector<std::vector<int>> levels;
    if (root == nullptr) return levels;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int count = q.size();
        std::vector<int> level;
        for (int i = 0; i < count; 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);
        }
        levels.push_back(level);
    }
    return levels;
}

List<List<Integer>> levelsOf(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<>();
    if (root == null) return levels;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        int count = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            TreeNode node = q.poll();
            level.add(node.val);
            if (node.left != null)  q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
        levels.add(level);
    }
    return levels;
}

function levelsOf(root) {
  const levels = [];
  if (root === null) return levels;
  let q = [root];
  while (q.length > 0) {
    const level = [], next = [];
    for (const node of q) {
      level.push(node.val);
      if (node.left)  next.push(node.left);
      if (node.right) next.push(node.right);
    }
    levels.push(level);
    q = next;
  }
  return levels;
}

from collections import deque

def levels_of(root):
    levels = []
    if root is None:
        return levels
    q = deque([root])
    while q:
        count = len(q)
        level = []
        for _ in range(count):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        levels.append(level)
    return levels

Complexity

Time: O(n) — each node is enqueued and dequeued once.
Space: O(w) where w is the maximum width of the tree (the largest level). For a balanced tree this is up to about n/2, i.e. O(n) in the worst case.

Going deeper: Level-order is just breadth-first search on a tree. The same queue technique finds shortest paths in unweighted graphs.

Next steps

You can now walk a tree both deep and wide. Apply it to ordered data with binary search trees, or practice on the tree exercises.