Binary Tree Level Order Traversal

Imagine drawing a tree on a whiteboard and reading it out loud one row at a time: first the root, then everything one step below it, then everything two steps below it, and so on. That row-by-row reading is a level order traversal (also called a breadth-first traversal). You'll implement binaryTreeLevelOrderTraversal(root), which takes the root of a binary tree and returns its values grouped into one array per level, top to bottom, and left to right within each level.

This shows up any time depth means something: rendering a comment thread by reply-depth, laying out an org chart rank by rank, or computing a tree's "right-side view." The grouping by level is the whole point — a flat list of values would lose which row each value sat on.

Signature

// A node in the binary tree. Either child may be null.
type TreeNode = {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
};

// root: the top node of the tree, or null for an empty tree.
// returns: an array of levels; each level is an array of that row's
//          node values, ordered left to right.
function binaryTreeLevelOrderTraversal(root: TreeNode | null): number[][];

Examples

A three-level tree. The root 3 is level 0; its children 9 and 20 are level 1; 20's children 15 and 7 are level 2:

//        3
//       / \
//      9   20
//         /  \
//        15   7
const root = {
  val: 3,
  left: { val: 9, left: null, right: null },
  right: {
    val: 20,
    left: { val: 15, left: null, right: null },
    right: { val: 7, left: null, right: null },
  },
};

binaryTreeLevelOrderTraversal(root);
// => [[3], [9, 20], [15, 7]]

A single node is a tree with exactly one level:

binaryTreeLevelOrderTraversal({ val: 1, left: null, right: null });
// => [[1]]

Notes

• Empty tree — if root is null, return [] (an empty array, not [[]]).
• Left to right — within a level, a node's left child comes before its right child, and earlier parents' children come before later parents' children.
• Values, not nodes — each inner array holds the val of each node, not the node objects themselves.
• Missing children — left or right may be null independently; a null child contributes nothing to the next level (no placeholder, no gap).
• Duplicates allowed — different nodes may share the same val; return each occurrence.