The preorder uses an arraylist and a stack (via LinkedList). It first pushes the root into the stack; then pops up the top of the stack (root here), adds that to the arraylist, pushes its right child and then left child into the stack; then pops the leftmost child so far, adds it to the arraylist, pushes its right child and then left child into the stack; then …

```/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> ret = new ArrayList<Integer>();
if(root != null)
stack1.push(root);
while(stack1.size() != 0) {
TreeNode top = stack1.pop();

if(top.right != null)
stack1.push(top.right);
if(top.left != null)
stack1.push(top.left);
}

return ret;
}
}
```

The post-order adds another stack to reverse the first stack, and then adds them to the arraylist.

```/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ArrayList<Integer> postorderTraversal(TreeNode root) {
if(root != null)
stack1.push(root);
while(stack1.size() != 0) {
TreeNode top = stack1.pop();
stack2.push(top);
if(top.left != null)
stack1.push(top.left);
if(top.right != null)
stack1.push(top.right);
}
ArrayList<Integer> ret = new ArrayList<Integer>();
while(stack2.size() != 0) {
}
return ret;
}
}
```

In-order traversal could be solved using an arraylist and a stack too. We will not stop push left value until we reach a null. We then backtrack and pop a value (the first popped value is the left-most leaf). And then start traverse its right child. And then start the above process again.
Test case:
[]
[1]
[1, #, 2]

confused what `"{1,#,2,3}"` means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

```   1
/ \
2   3
/
4
\
5
```

The above binary tree is serialized as `"{1,2,3,#,#,4,#,#,5}"`.

```/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ArrayList<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> ret = new ArrayList<Integer>();
TreeNode current = root;

boolean done = false;
while(true) {
if(current != null) {
stack.push(current);
current = current.left;
} else {
if(stack.size() == 0)
break;
else {
current = stack.pop();