Binary Tree Level-Order Traversal

time: O(n)
space: O(w)
tags: trees · bfs

in the wild Wavefront expansion on an occupancy grid, organizational-chart visualization (one level per row), and 'show me the network neighbors at depth ≤ k'.

Problem

Given the root of a binary tree, return its values grouped by level — a list of lists, where the i-th list contains every node at depth i (root is depth 0), in left-to-right order.

Examples

        3
       / \             → [[3], [9, 20], [15, 7]]
      9  20
         / \
        15  7

       1
        \              → [[1], [2]]
         2

     (empty)            → []

Why this is the canonical "tree meets queue" problem

Recursion's natural traversal is depth-first — left subtree all the way down, then right. Going level-by-level (breadth-first) requires iterating across siblings before going deeper. The queue is what makes that work:

Enqueue the root.
While the queue isn't empty, snapshot its length (= number of nodes on the current level), then for that many iterations pop a node, record its value into the current level's list, enqueue its children.
Each while-iteration of step 2 produces one level.

This is the same BFS pattern you'll see in the graphs lesson, specialized to trees (no visited set needed because trees have no cycles). It generalizes to "find shortest unweighted path", "list nodes at distance ≤ k", and "find nearest common ancestor by depth".

Hints

Hint 1 — what to use besides recursion

The natural recursive traversals (pre/in/post-order) all go deep before wide. To go wide-first, you want to process nodes in the order they're discovered — that's a FIFO. Which structure pops oldest-first?

Hint 2 — knowing where one level ends

If you just pop one node at a time, you don't know when level 0 ends and level 1 begins. Solution: at the top of each outer iteration, freeze the queue's current size — that's exactly the number of nodes at the current level. Process that many before moving on.

Hint 3 — pseudocode

result = []
queue  = [root]   if root else []
while queue:
    level_size = len(queue)
    level      = []
    for _ in range(level_size):
        node = queue.popleft()
        level.append(node.val)
        if node.left:  queue.append(node.left)
        if node.right: queue.append(node.right)
    result.append(level)

Solution

from collections import deque
from dataclasses import dataclass
from typing import Optional

@dataclass
class Node:
    val: int
    left:  Optional["Node"] = None
    right: Optional["Node"] = None

def level_order(root: Optional[Node]) -> list[list[int]]:
    if root is None:
        return []
    out: list[list[int]] = []
    q: deque[Node] = deque([root])
    while q:
        # Snapshot — only this many nodes belong to the current level.
        size  = len(q)
        level = []
        for _ in range(size):
            n = q.popleft()
            level.append(n.val)
            if n.left:  q.append(n.left)
            if n.right: q.append(n.right)
        out.append(level)
    return out

t1 = Node(3, Node(9), Node(20, Node(15), Node(7)))
t2 = Node(1, None, Node(2))
t3 = None
cases = [
    (t1, [[3], [9, 20], [15, 7]]),
    (t2, [[1], [2]]),
    (t3, []),
]
for root, expected in cases:
    got  = level_order(root)
    mark = "✓" if got == expected else "✗"
    print(f"{mark} level_order(...) = {got}")

class Node {
  constructor(val, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

function levelOrder(root) {
  if (root === null) return [];
  const out = [];
  let q = [root];
  while (q.length) {
    const size  = q.length;
    const level = [];
    const next  = [];
    for (let i = 0; i < size; i++) {
      const n = q[i];
      level.push(n.val);
      if (n.left)  next.push(n.left);
      if (n.right) next.push(n.right);
    }
    out.push(level);
    q = next;                            // swap arrays — avoid shift(), which is O(n)
  }
  return out;
}

const t1 = new Node(3, new Node(9), new Node(20, new Node(15), new Node(7)));
const t2 = new Node(1, null, new Node(2));
const t3 = null;
const cases = [
  [t1, [[3], [9, 20], [15, 7]]],
  [t2, [[1], [2]]],
  [t3, []],
];
for (const [root, expected] of cases) {
  const got = levelOrder(root);
  const ok  = JSON.stringify(got) === JSON.stringify(expected);
  console.log(`${ok ? "✓" : "✗"} levelOrder(...) = ${JSON.stringify(got)}`);
}

use std::collections::VecDeque;

pub struct Node {
    pub val:   i32,
    pub left:  Option<Box<Node>>,
    pub right: Option<Box<Node>>,
}

// We borrow the tree non-destructively via &Box<Node>.
pub fn level_order(root: Option<&Box<Node>>) -> Vec<Vec<i32>> {
    let mut out = Vec::new();
    let Some(root) = root else { return out; };

    let mut q: VecDeque<&Box<Node>> = VecDeque::new();
    q.push_back(root);
    while !q.is_empty() {
        let size = q.len();
        let mut level = Vec::with_capacity(size);
        for _ in 0..size {
            let n = q.pop_front().unwrap();
            level.push(n.val);
            if let Some(ref l) = n.left  { q.push_back(l); }
            if let Some(ref r) = n.right { q.push_back(r); }
        }
        out.push(level);
    }
    out
}

fn leaf(v: i32) -> Option<Box<Node>> {
    Some(Box::new(Node { val: v, left: None, right: None }))
}
fn node(v: i32, l: Option<Box<Node>>, r: Option<Box<Node>>) -> Option<Box<Node>> {
    Some(Box::new(Node { val: v, left: l, right: r }))
}

fn main() {
    let t1 = node(3, leaf(9), node(20, leaf(15), leaf(7)));
    let t2 = node(1, None, leaf(2));
    let t3: Option<Box<Node>> = None;
    let cases: &[(Option<&Box<Node>>, Vec<Vec<i32>>)] = &[
        (t1.as_ref(), vec![vec![3], vec![9, 20], vec![15, 7]]),
        (t2.as_ref(), vec![vec![1], vec![2]]),
        (t3.as_ref(), vec![]),
    ];
    for (root, expected) in cases {
        let got  = level_order(*root);
        let mark = if got == *expected { "✓" } else { "✗" };
        println!("{mark} level_order(...) = {:?}", got);
    }
}

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

struct Node {
    int   val;
    Node* left;
    Node* right;
    Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};

std::vector<std::vector<int>> level_order(Node* root) {
    std::vector<std::vector<int>> out;
    if (!root) return out;
    std::queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        int size = (int)q.size();
        std::vector<int> level;
        level.reserve(size);
        for (int i = 0; i < size; ++i) {
            Node* n = q.front(); q.pop();
            level.push_back(n->val);
            if (n->left)  q.push(n->left);
            if (n->right) q.push(n->right);
        }
        out.push_back(std::move(level));
    }
    return out;
}

static void show(const std::vector<std::vector<int>>& v) {
    std::cout << "[";
    for (size_t i = 0; i < v.size(); ++i) {
        std::cout << "[";
        for (size_t j = 0; j < v[i].size(); ++j)
            std::cout << v[i][j] << (j + 1 < v[i].size() ? "," : "");
        std::cout << "]" << (i + 1 < v.size() ? "," : "");
    }
    std::cout << "]";
}

int main() {
    Node* t1 = new Node(3, new Node(9), new Node(20, new Node(15), new Node(7)));
    Node* t2 = new Node(1, nullptr, new Node(2));
    Node* t3 = nullptr;
    std::cout << "✓ level_order(t1) = "; show(level_order(t1)); std::cout << "\n";
    std::cout << "✓ level_order(t2) = "; show(level_order(t2)); std::cout << "\n";
    std::cout << "✓ level_order(t3) = "; show(level_order(t3)); std::cout << "\n";
}

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int          val;
    struct Node* left;
    struct Node* right;
} Node;

// Print one level worth (length n) of the result. The caller drives the BFS.
void level_order(Node* root) {
    if (!root) { printf("[]\n"); return; }
    // BFS queue as a ring buffer of pointers. Conservative size: 1024 fits demos.
    Node*  queue[1024];
    int    head = 0, tail = 0;
    queue[tail++] = root;
    printf("[");
    int first_level = 1;
    while (head < tail) {
        int size = tail - head;
        if (!first_level) printf(",");
        first_level = 0;
        printf("[");
        for (int i = 0; i < size; i++) {
            Node* n = queue[head++];
            printf("%d%s", n->val, i + 1 < size ? "," : "");
            if (n->left)  queue[tail++] = n->left;
            if (n->right) queue[tail++] = n->right;
        }
        printf("]");
    }
    printf("]\n");
}

static Node* mk(int v, Node* l, Node* r) {
    Node* n = malloc(sizeof(Node));
    n->val = v; n->left = l; n->right = r;
    return n;
}

int main(void) {
    Node* t1 = mk(3, mk(9, NULL, NULL), mk(20, mk(15, NULL, NULL), mk(7, NULL, NULL)));
    Node* t2 = mk(1, NULL, mk(2, NULL, NULL));
    printf("✓ level_order(t1) = "); level_order(t1);
    printf("✓ level_order(t2) = "); level_order(t2);
    printf("✓ level_order(NULL) = "); level_order(NULL);
    return 0;
}

idle

The "snapshot the queue size before processing the level" trick is the key idea — without it you can still BFS but you lose the level groupings. JavaScript's array .shift() is O(n), so the JS solution swaps in a fresh next array per level instead — same big-O, much faster in practice.

Complexity

Time: O(n) — each node is enqueued exactly once, dequeued exactly once, and contributes O(1) work.
Space: O(w) where w is the widest level. For a perfect binary tree of n nodes, w ≈ n/2 at the bottom.
vs DFS: You can do level grouping with DFS (pass depth down, append into result[depth]) — same time, O(h) stack space, but the right-then-left order on each level needs careful handling.

In the wild

Wavefront path planning on an occupancy grid is exactly level-order BFS — the wavefront is the queue snapshot. See the graphs lesson grid mode.
Friends-of-friends queries. "Show me people within 2 hops" on a social graph is level-order BFS capped at depth 2.
Concurrent / batched work. Compute layer L+1's outputs from all of layer L's outputs in parallel — neural-net forward pass is conceptually level-order over the computation DAG.
Tree-printing renderers. Org-chart, family-tree, and Mermaid layout engines all process one level before moving to the next so they can compute horizontal positions.

Variations

Zigzag level order. Reverse alternating levels (L→R, R→L, L→R, …). Two-line tweak: reverse level when len(out) % 2 == 1.
Right-side view. Just the last element of each level — the silhouette from the right.
Per-level average. Mean of each level. Trivial extension.
Cousins check. Two nodes are cousins iff they're on the same level but have different parents. Level-order with parent tracking nails this.