Pre-order Traversal
by Isai Damier, Android Engineer @ Google

/**********************************************************************
 * Author: Isai Damier
 * Title: Pre-order Traversal
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Time Complexity of Solution:
 *   Best = Average = Worst = O(n).
 *
 * Description: visit node; visit left child; visit right child.
 *    All the left nodes are visited first, effectively.
 *    But a parent is visited before its children.
 *
 * Technical Details:
 *    0] preliminary checks:
 *       1) return if root is null;
 *       2) create pointer n
 *    1] create a stack and add root to it;
 *    2] while stack is not empty
 *       1) pop stack into n
 *       2) visit node n
 *       3) push right child then left child of node n to stack
 *        if they are not null.
 *
 * Alternate Algorithm: recursive:
 *
 *     public void preorder(){
 *       preorder(root);
 *     }
 *
 *     public void preorder(Node n){
 *       if(null != n){
 *         visit(n);
 *         preorder(n.left);
 *         preorder(n.right);
 *       }
 *     }
 *
 *********************************************************************/ 
 public void preorder() {
  if (null == root) {
    return;
  }
  Node n;
  Stack<Node> stack = new Stack<Node>();
  stack.push(root);

  while (!stack.isEmpty()) {
    n = stack.pop();//pop last node added
    visit(n);
    if (null != n.right) {
      stack.push(n.right);
    }
    if (null != n.left) {
      stack.push(n.left);
    }
  }
}

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 preorder method, of class BST.
   */
  @Test
  public void testPreorder() {
    System.out.println(""preorder"");
    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};

    Integer[] pre = {200, 100, 50, 25, 35, 75, 150, 125, 175, 300, 250, 225,
      212, 275, 350, 325, 312, 375, 400};
    String expected = """";
    assertEquals(expected, output.toString());
    for (int i : pre) {
      expected += i + ""\n"";
    }

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

    //test preorder
    bst.preorder();
    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"");
  }

}