Reading a tree one level at a time

Report the values of a binary tree in level order: the root first, then everything one step below it, then everything two steps below, and so on. Within a level, read left to right.

Worked example#

      3
     / \
    9   20
       /  \
      15   7

Level order is 3 9 20 15 7.

The idea#

Every other traversal you have written is recursive, and recursion goes deep first: it follows one child all the way down before looking at the other. Level order needs the opposite, and that is why it is the one traversal you cannot write naturally with recursion.

Use a queue. Put the root in it, then repeatedly take a node off the front, record it, and put its children on the back. Because children always go behind everything already waiting, a node at depth 2 can never come out before a node at depth 1.

That is the whole algorithm, and it is worth noticing how directly the structure answers the question. A stack would give you depth first. A queue gives you breadth first. The choice of container is the algorithm.

The pattern this starts#

Breadth-first search on a graph is the same loop with a "have I been here" check added. Once you can write this, that is a small step rather than a new idea.

Constraints#

• 0 <= number of nodes <= 100000

About the input#

The tree is written level by level with null for a missing child, the count first. So 7 / 3 9 20 null null 15 7 is the tree above.