# Level Order Traversalby 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;
}

Node n;

while (!q.isEmpty()) {
n = q.remove();//dequeue FIFO
visit(n);
if (null != n.left) {
}
if (null != 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"";
}