Binary Tree Level Order Traversal

MEDIUM✓ CHIP-TIMEDLC #102 — FULL STATEMENT ↗

The drill: Read a binary tree out floor by floor — one inner list per depth, each holding that depth's values left to right.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A binary tree arrives, and the task is to read it out floor by floor — every node grouped by how deep it sits, and within each floor, ordered left to right.

The result is a list of lists: one inner list per depth level, starting from the root's own level at index zero and working downward, each inner list holding that level's values in left-to-right order.

An empty tree produces an empty outer list, since there are no floors at all to report.

EX 01

root = []

→ []

EMPTY TREE

EX 02

root = [1]

→ [[1]]

SINGLE NODE

EX 03

root = [3, 9, 20, null, null, 15, 7]

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

CLASSIC UNBALANCED SHAPE

the tree can hold anywhere from zero to a few thousand nodes
node values can be negative, zero, or positive
each depth level becomes its own list, ordered root-level first, left to right within a level

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Depth is the whole organizing idea. What lets you process an entire floor of the tree together instead of node by node?

HINT 2 THE STRUCTURE

A queue that holds exactly one depth's worth of nodes at a time turns the tree into a sequence of flat batches.

HINT 3 ONE STEP FROM THE ANSWER

Snapshot the queue's current size before touching it — that count is exactly this floor's node count. Drain that many, collecting values and queuing their children for the next floor.

COACH'S BOARD — THE PATTERN, STEP BY STEP

FLOOR BY FLOORPATTERN · QUEUE BY FLOORroot = [3, 9, 20, null, null, 15, 7]

QUEUE

STEP 1

BFS by floor: seed the queue with the root, then drain exactly that many nodes each round — one round per depth.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/binary-tree-level-order-traversal.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        out = []
        queue = [root]
        while queue:
            level = []
            nxt = []
            for node in queue:
                level.append(node.val)
                if node.left:
                    nxt.append(node.left)
                if node.right:
                    nxt.append(node.right)
            out.append(level)
            queue = nxt
        return out

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 18 LN

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        def height(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            return 1 + max(height(node.left), height(node.right))

        def collect(node: Optional[TreeNode], depth: int, target: int, bucket: List[int]) -> None:
            if not node:
                return
            if depth == target:
                bucket.append(node.val)
                return
            collect(node.left, depth + 1, target, bucket)
            collect(node.right, depth + 1, target, bucket)

        h = height(root)
        out = []
        for d in range(h):
            bucket: List[int] = []
            collect(root, 0, d, bucket)
            out.append(bucket)
        return out

TIME O(N·H)SPACE O(N)PYTHON · TRAINING PACE · 26 LN

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> out = new ArrayList<>();
        if (root == null) {
            return out;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            out.add(level);
        }
        return out;
    }
}

TIME O(N)SPACE O(N)JAVA · RACE PACE · 26 LN

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> out = new ArrayList<>();
        if (root == null) {
            return out;
        }
        int h = height(root);
        for (int d = 0; d < h; d++) {
            List<Integer> bucket = new ArrayList<>();
            collect(root, 0, d, bucket);
            out.add(bucket);
        }
        return out;
    }

    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }

    private void collect(TreeNode node, int depth, int target, List<Integer> bucket) {
        if (node == null) {
            return;
        }
        if (depth == target) {
            bucket.add(node.val);
            return;
        }
        collect(node.left, depth + 1, target, bucket);
        collect(node.right, depth + 1, target, bucket);
    }
}

TIME O(N·H)SPACE O(N)JAVA · TRAINING PACE · 34 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED