# In-order Traversalby 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};

for (int i : treeTape) {
}
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"");
}
}```