Binary Tree Level Order Traversal

MediumTreesTreeBFSBinary Tree

Problem

Given the root of a binary tree, return the values of its nodes grouped level by level, from the root's level down to the deepest leaves, with each level's values listed left to right.

Example. A root 3 with left child 9 and right child 20, where 20 has children 15 and 7, produces the grouped output [3], [9, 20], [15, 7], one list per depth.

Key idea

A standard depth-first traversal visits nodes in an order that mixes depths together, so producing grouped-by-level output would require tagging every node with its depth and bucketing afterward: extra bookkeeping the problem does not need.

Breadth-first search naturally processes one level at a time, so it fits directly. Start with a queue holding just the root. Before touching the queue for a round, record how many nodes are currently in it: that count is exactly the size of the current level, since nothing deeper has been added yet. Pop that many nodes, collect their values into the level's list, and as each is popped, push its non-null children onto the back of the queue for the next round. When the recorded count is exhausted, the level is complete, and the newly queued nodes form the next one. Continue until the queue is empty. Depth-first search can also produce level groupings by passing the depth down through the recursion, but the queue-based sweep is the more direct fit here.

Solution

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function levelOrder(root: TreeNode | null): number[][] {
  const levels: number[][] = [];
  if (root === null) {
    return levels;
  }

  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    // snapshot the size before enqueueing next-level nodes, so this round stays fixed
    const levelSize = queue.length;
    const level: number[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift() as TreeNode;
      level.push(node.val);

      // queue non-null children for the next level's round
      if (node.left !== null) {
        queue.push(node.left);
      }
      if (node.right !== null) {
        queue.push(node.right);
      }
    }

    levels.push(level);
  }

  return levels;
}

Complexity

  • Time: O(n). Every node is enqueued and dequeued exactly once.
  • Space: O(n). The queue holds up to a full level of nodes at once, and the output stores every node's value.

Watch out for

  • Snapshot the queue's size at the start of each level before popping; popping without that fixed count blends two levels together.
  • An empty tree should return an empty result rather than a single empty level.
  • Enqueue only non-null children, or the queue fills with sentinel values that corrupt the level counts.

Pattern

This is the canonical breadth-first level-by-level sweep, the same queue-and-level-size technique used for right-side-view traversals, shortest paths in unweighted graphs, and any task phrased in terms of distance from the root or minimum number of steps.

Related questions