← Index

Trees

Binary Tree Level Order TraversalMedium

Given the root of a binary tree, return its node values grouped level by level, top to bottom, left to right within each level.

Examples

Approach

BFS with a queue is the natural fit, since 'level by level' is exactly what BFS explores in. The trick to grouping output by level: before processing a batch of nodes, snapshot the queue's current length — that's exactly how many nodes belong to the current level. Process precisely that many, pushing their children for the next round.

Complexity — best & worst case

Code

// Given the root of a binary tree, return its node values grouped
// level by level (top to bottom, left to right within a level).

class TreeNode {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

// --- BFS with a queue: the natural fit for "level by level" ---
// Process one full level at a time by snapshotting the queue's
// current length before adding that level's children.
function levelOrder(root) {
  if (!root) return [];

  const result = [];
  const queue = [root];

  while (queue.length) {
    const levelSize = queue.length;
    const level = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

// --- Alternative: DFS while tracking depth (works, but BFS reads cleaner
// for a "level by level" problem since it matches the traversal order) ---
function levelOrderDFS(root) {
  const result = [];
  function dfs(node, depth) {
    if (!node) return;
    if (!result[depth]) result[depth] = [];
    result[depth].push(node.value);
    dfs(node.left, depth + 1);
    dfs(node.right, depth + 1);
  }
  dfs(root, 0);
  return result;
}

// --- Example Usage ---
//         3
//        / \
//       9  20
//          /  \
//         15   7
const root = new TreeNode(3,
  new TreeNode(9),
  new TreeNode(20, new TreeNode(15), new TreeNode(7)),
);

console.log(levelOrder(root));    // [[3], [9,20], [15,7]]
console.log(levelOrderDFS(root)); // [[3], [9,20], [15,7]]