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

for (int i : treeTape) {