Level-order in Code

The three steps from the previous section translate almost directly into code:

public static <T> void levelOrder(Node<T> root) {
  if (root == null) {
    return;  // an empty tree has nothing to visit
  }
  Queue<Node<T>> queue = new LinkedQueue<>();
  queue.enqueue(root);                 // start with the root waiting
  while (!queue.isEmpty()) {
    Node<T> node = queue.front();      // the oldest node waiting
    queue.dequeue();                   // remove it from the front
    System.out.println(node.value);    // visit
    if (node.left != null) {
      queue.enqueue(node.left);        // enqueue the children at the back
    }
    if (node.right != null) {
      queue.enqueue(node.right);
    }
  }
}

The Queue here is the one we built in the queue chapter, instantiated as a LinkedQueue (the ArrayQueue from that same chapter would work just as well). Our dequeue does not return the node it removes, so we read the front with front first and then drop it with dequeue.

We check each child against null before enqueuing. Our enqueue rejects null, so without the check the loop would throw at the first leaf.

The cost

Every node enters the queue exactly once, when its parent is visited (or at the very start, for the root), and leaves exactly once, when it is visited. The work done for each node (a dequeue, a print, and up to two enqueues) is constant. So the whole traversal is linear in the number of nodes.

The recursive attempt revisited the top of the tree once per level and needed a separate pass to find the height. Here the waiting nodes are already stored in the queue, so the traversal never has to walk down from the root to find them again.