Level-Order Traversal

A binary tree is built from Node objects. Each node holds a value and references to its left and right subtrees. A null reference is the empty tree:

public class Node<T> {
  public T value;
  public Node<T> left;
  public Node<T> right;
}

To visit a node means to print its value.

You have this Queue interface, implemented by LinkedQueue, with every operation in $O (1)$ time:

public interface Queue<T> {
  void enqueue(T value);  // adds value at the back
  void dequeue();         // removes the front value
  T front();              // returns the front value
  boolean isEmpty();      // returns true if the queue is empty
}

enqueue throws an IllegalArgumentException if value is null. dequeue and front throw a NoSuchElementException if the queue is empty.

Here is a binary tree:

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

Node 5 has only a right child, and node 9 has only a left child.

Solution

6   2   9   5   1   3   8   7   4

Solution

Once a call recurses into one child, it finishes that child’s whole subtree before it returns to the other child. Level-order needs 2 and 9 one after the other. But a recursion that goes from 6 into 2 visits 5, 8, and 1 before it comes back for 9. The call stack always resumes the most recently deferred work, while level-order needs the node that was found earliest.

Solution

public static <T> void levelOrder(Node<T> root) {
  if (root == null) {
    return;
  }
  Queue<Node<T>> queue = new LinkedQueue<>();
  queue.enqueue(root);
  while (!queue.isEmpty()) {
    Node<T> node = queue.front();
    queue.dequeue();
    System.out.println(node.value);
    if (node.left != null) {
      queue.enqueue(node.left);
    }
    if (node.right != null) {
      queue.enqueue(node.right);
    }
  }
}

Solution

start                            [6]
visit 6, enqueue 2 and 9         [2 9]
visit 2, enqueue 5 and 1         [9 5 1]
visit 9, enqueue 3               [5 1 3]
visit 5, enqueue 8               [1 3 8]
visit 1                          [3 8]
visit 3, enqueue 7 and 4         [8 7 4]
visit 8                          [7 4]
visit 7                          [4]
visit 4                          []

Solution

$O (n)$ . Each node is enqueued once and dequeued once, and the work for each node is a constant number of $O (1)$ queue operations and a print.