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

/****************************************************************
 *  Author: Isai Damier
 * Title: In-order Traversal
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Time Complexity of Solution:
 *   Best = Average = Worst = O(n).
 *
 * Description: visit left child; visit node; visit right child.
 *    This techniques visits a BST in sorted order.
 *
 * Technical Details:
 *    0]preliminary check:
 *       1) create stack
 *    2] declare node n and set it to root
 *    3] while n is not null or stack is not empty
 *       1) if n is not null THEN
 *         add n to stack and set n to n.left
 *       2) ELSE pop stack into n, visit n, and set n to n.right
 *
 * Alternate Algorithm: recursive:
 *
 *     public void inorder(){
 *       inorder(root);
 *     }
 *
 *     public void inorder(Node n){
 *       if(null != n){
 *         inorder(n.left);
 *         visit(n);
 *         inorder(n.right);
 *       }
 *     }
 ***************************************************************/ 
 public void inorder() {
  Node n = root;
  Stack<Node> stack = new Stack<Node>();

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

import org.junit.Test;
import static org.junit.Assert.*;

public class BSTTest {

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

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

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

    //test levelorder
    bst.inorder();//assumes visit() prints to screen
    Arrays.sort(treeTape);
    String result[] = output.toString().split(""\\D"");
    for (int i = 0; i < treeTape.length; i++) {
      if (treeTape[i] != Integer.parseInt(result[i])) {
        fail(""inorder traversal fails"");
      }
    }
    assertEquals(treeTape.length, bst.size());//has correct size
    System.setOut(new PrintStream(new FileOutputStream(FileDescriptor.out)));
    System.out.println(""done with inorder"");
  }
}