Traversing Level by Level

The three depth-first traversals each go all the way down one subtree before they move to the subtree beside it. Level-order traversal goes one level at a time instead. It starts at the top level and reads each level from left to right.

A level is the set of nodes at the same depth. The root is level 0, its children are level 1, their children level 2, and so on.

Here is our tree again:

                  ╭───╮
                  │ 5 │
                  ╰─┬─╯
         ┌──────────┴──────────┐
       ╭─┴─╮                 ╭─┴─╮
       │ 8 │                 │ 2 │
       ╰─┬─╯                 ╰─┬─╯
    ┌────┴────┐           ┌────┴────┐
  ╭─┴─╮     ╭─┴─╮       ╭─┴─╮     ╭─┴─╮
  │ 9 │     │ 1 │       │ 4 │     │ 7 │
  ╰─┬─╯     ╰───╯       ╰───╯     ╰─┬─╯
  ┌─┘                               └─┐
╭─┴─╮                               ╭─┴─╮
│ 6 │                               │ 3 │
╰───╯                               ╰───╯

Read it one level at a time:

level 0:   5
level 1:   8   2
level 2:   9   1   4   7
level 3:   6   3

Within each level, a left parent’s children come before a right parent’s: 8’s children 9 and 1 come before 2’s children 4 and 7.

Put the levels one after another, and the level-order is:

5   8   2   9   1   4   7   6   3

This is called a breadth-first traversal, because it covers the full width of one level before it goes a level deeper.