/**************************************************************************
* 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"");
}
}