PreOrder traversal is very similar to in-order traversal in terms of code. The idea behind pre-order traversal is to do all the processing before visiting the left subtree and the right subtree. I will use the stack data structures to keep a history of the visited elements, and used that as a map to backtrack.

### Setup

```
# 1
# / \
# 9 8
# / \ \
# 6 4 3
# / \ /
# 2 7 5
#
# Print out: 1 9 6 2 7 4 8 3 5
```

### TreeNode Definition

```
public static class TreeNode {
int data;
TreeNode left;
TreeNode right;
public TreeNode(int d) {
data = d;
left = null;
right = null;
}
}
```

### Time & Space

The time and space complexities for this algorithm are O(n) and O(log(n)) respectively. The time complexity is O(n) because I will need to visit all the elements to print them. The space complexity is O(log(n)) because the stack will have at most as many elements in it as the height of the tree.

### Iterative

```
public static void printPreOrder(TreeNode root) {
if (root == null) return;
Stack<TreeNode> parents = new Stack<TreeNode>();
TreeNode cur = root;
parents.push(cur);
while (!parents.isEmpty() || cur != null) {
if (cur != null) {
System.out.printf("%d ", cur.data);
parents.push(cur);
cur = cur.left;
}
else {
TreeNode parent = parents.pop();
cur = parent.right;
}
}
}
```

### Recursive

```
public static void printPreOrder(TreeNode root) {
if (root == null) return;
System.out.printf("%d ", root.data);
printInOrder(root.left);
printInOrder(root.right);
}
```