Level Order Traversal
by Isai Damier, Android Engineer @ Google

/**************************************************************************
 * Author: Isai Damier
 * Title: Level Order Traversal
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Time Complexity of Solution:
 *   Best = Average = Worst = O(n).
 *
 * Description: visit node; visit cousins; visit children and nephews.
 *   Level-order (aka breadth-first) traversal visits the elements of a
 *   binary search tree one level at a time. Image a BST as a family tree:
 *   with siblings and cousins and uncles, etc; level order, then, visits
 *   the nodes by generation. The grand-parent generation is visited first;
 *   then the parent generation; then the children generation.
 *
 * Technical Details: Of all the fundamental traversal techniques, level
 *   order is the only one that uses a queue. All the other techniques use
 *   a stack, because they are depth-first algorithms.
 *
 * 0] preliminary checks:
 *     1) return if root is null
 *     2) create queue
 * 1] add the root to the queue
 * 2] while the queue is not empty
 *     1) dequeue a node from the queue
 *     2) visit the node
 *     3) add the children of the node to the queue if they are not null
 *
 * Application:
 *    print BST to file then read file back as same BST
 *
 **************************************************************************/ 
 public void levelorder() {
  if (null == root) {
    return;
  }

  Queue<Node> q = new LinkedList<Node>();
  q.add(root);
  Node n;

  while (!q.isEmpty()) {
    n = q.remove();//dequeue FIFO
    visit(n);
    if (null != n.left) {
      q.add(n.left);
    }
    if (null != n.right) {
      q.add(n.right);
    }
  }
}
import java.io.ByteArrayOutputStream;
import java.io.FileDescriptor;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;

public class BSTTest {

/**
   * Test of levelorder method, of class BST.
   */
  @Test
  public void testLevelorder() {
    System.out.println(""levelorder"");
    final ByteArrayOutputStream output = new ByteArrayOutputStream();
    System.setOut(new PrintStream(output));

    BST bst = new BST();
   Integer[] treeTape = {200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
      175, 225, 275, 325, 375, 35, 212, 312, 400};

    //set expectation
    String expected = """";
    assertEquals(expected, output.toString());
    for (int i : treeTape) {
      expected += i + ""\n"";
    }

    //add elements to tree
    for (int i : treeTape) {
      bst.add(i);
    }
    assertEquals(treeTape.length, bst.size());//has correct size

    //test levelorder
    bst.levelorder();//assumes visit() prints to screen
    assertEquals(expected, output.toString());
    assertEquals(treeTape.length, bst.size());//has correct size
    System.setOut(new PrintStream(new FileOutputStream(FileDescriptor.out)));
    System.out.println(""done with levelorder"");
  }
}