# BinaryTree InOrder Traversal in JAVA

This is my iterative and recursive implementation of the InOrder traversal method on a BinaryTree data structure. InOrder traversal is a form of depth first traversal, so I will be using a the Stack data structure to keep a history of the visited TreeNode and backtrack once I have reached the end of a branch. The idea behind this algorithm is to visit all the nodes on the left subtree, the root, then all the nodes on the right subtree. This method simply prints all the data in the TreeNode. I will start with the TreeNode definition.

### TreeNode Definition

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

### Iterative

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

### Recursive

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