Level order traversal (BFS)

Medium TimeO(n) SpaceO(n)

Level order reads a tree in rows: the root, then everything one step below it, then everything two steps below, with each row kept separate. Given the root of a binary tree, return those rows, each as its own array. Within a row the nodes are read left to right, and an empty tree produces an empty list.

Examples

Example 1

Input
root = buildTree()
Output
[[4],[2,7],[1,3,6,9]]
Row by row: the root 4, then 2, 7, then the four leaves left to right.

Example 2

Input
root = buildTree().left
Output
[[2],[1,3]]
The left subtree on its own has two rows: 2, and then 1, 3.

The Code

function buildTree() {
  return {
    val: 4,
    left: { val: 2, left: { val: 1, left: null, right: null }, right: { val: 3, left: null, right: null } },
    right: { val: 7, left: { val: 6, left: null, right: null }, right: { val: 9, left: null, right: null } }
  };
}
function levelOrder(root) {
  const levels = [];
  let current = root === null ? [] : [root];
  while (current.length > 0) {
    const values = [];
    const next = [];
    for (let i = 0; i < current.length; i++) {
      const node = current[i];
      values.push(node.val);
      if (node.left !== null) next.push(node.left);
      if (node.right !== null) next.push(node.right);
    }
    levels.push(values);
    current = next;
  }
  return levels;
}
levelOrder(buildTree());
Done
Step through levelOrder(buildTree()) call by call

More like this

All binary trees examples (9) →