Trying Recursion

The three depth-first orders came from recursion, so it is natural to try recursion again.

The recursive template is depth-first

Every traversal we wrote had the same three pieces: visit the node, recurse left, recurse right. Whatever order we put them in, the recursion runs a child’s entire subtree before it comes back for the other child.

Level-order needs 8 and 2, the two nodes on level 1, to come out one after the other.

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

But any recursion that goes from 5 into 8 runs all of 8’s descendants, 9, 1, and 6, before it returns to take 2. No order of the three pieces fixes this.

One level per pass

We can still produce level-order with recursion by handling one level per pass. Write a helper that prints only the nodes at a chosen depth,

public static <T> void printLevel(Node<T> node, int level) {
  if (node == null) {
    return;
  }
  if (level == 0) {
    System.out.println(node.value);  // reached the target depth
    return;
  }
  printLevel(node.left, level - 1);
  printLevel(node.right, level - 1);
}

and then call it once for each level, from the top down to the height we measured earlier:

public static <T> void levelOrder(Node<T> root) {
  int h = height(root);
  for (int level = 0; level <= h; level++) {
    printLevel(root, level);
  }
}

This does print 5 8 2 9 1 4 7 6 3, the order we want, but it is wasteful. Every call to printLevel starts over at the root and descends. To print level 3, the two nodes 6 and 3, it descends from 5 through every level above them. So the top of the tree is touched once for every level beneath it, while a depth-first traversal touches each node once. On a tall, thin tree the total work grows with the square of the number of nodes.^[1] We also had to compute the height first, an extra pass over the tree, just to know when to stop.

The call stack

Recursion runs on the call stack. When a call steps into the left child, the work for the right child waits in that call’s stack frame until the whole left subtree is done. So the call stack always goes back to the most recently deferred work first. Level-order needs the reverse. Among the nodes we have seen but not yet visited, we want to take the one we met earliest.