All the Tree Traversal you need (not recursively!)

Preorder

Using a stack.

Update 2015 - 03 - 05: 
DFS

public class PreOrder {
    public List preorderTraversal(TreeNode root) {
        ArrayList rst = new ArrayList();
        if (root == null)
            return rst;
        Stack stack = new Stack();
        stack.push(root);
        while(!stack.empty())
        {
            TreeNode tmp = stack.pop();
            rst.add(tmp.val);
            if (tmp.right != null)
                stack.add(tmp.right);
            if (tmp.left != null)
                stack.add(tmp.left);
        }
        return rst;
    }
}

The recursion method:

public List preorderTraversal(TreeNode root) {
        List rst = new ArrayList ();
        preOrder(root, rst);
        return rst;
    }
    private void preOrder(TreeNode root, List rst) {
        if (root == null)
            return;
        rst.add(root.val);
        preOrder(root.left, rst);
        preOrder(root.right, rst);
    }

Inorder

Update: 2015 - 01 - 06
Inorder tree traversal is basically DFS. If not using recursion, then a stack is required. The problem here is how to mark visited node, i.e., when we traverse back from the bottom, how can we not redundantly traverse the left branch again. In this method, instead of pushing the root outside the loop, I put it into the loop. If the current node is not null, we push the node, and traverse down to its left branch. when we are at the left most leaf, current node will point to null. Then it's the time to pop out nodes from the stack and check its right side.

public class InOrder {
    public List inorderTraversal(TreeNode root) {
        ArrayList rst = new ArrayList();
        if (root == null)
            return rst;
        TreeNode node = root;
        Stack stack = new Stack ();
        while (!stack.empty() || node != null)
        {
            //traverse down to the left
            if (node != null)
            {
                stack.push(node);
                node = node.left;
            }
            else
            {
                TreeNode tmp = stack.pop();
                rst.add(tmp.val);
                node = tmp.right;
            }
        }
        return rst;
    }
}

Postorder

public class PostOrder {
    public ArrayList postorderTraversal(TreeNode root) {
        ArrayList rst = new ArrayList();
        if (root == null)
            return rst;
        Stack stack = new Stack();
        TreeNode curr = null;
        TreeNode prev = null;
        stack.push(root);
        while (!stack.empty())
        {
            curr = stack.peek();
            //prev == null, root
            //traverse down
            if (prev == null || prev.left == curr || prev.right == curr)
            {
                if (curr.left != null)
                    stack.push(curr.left);
                //need to traverse to the bottom of the tree first before goes to the right side
                else if (curr.right != null)
                    stack.push(curr.right);
            }
            // here comes the right side
            else if (curr.left == prev)
            {
                if (curr.right != null)
                    stack.push(curr.right);
            }
            //finally we can add nodes
            else
            {
                rst.add(curr.val);
                stack.pop();
            }
            prev = curr;
        }
        return rst;
    }
}

Level Order

public class LevelOrder {
    public ArrayList> levelOrder(TreeNode root) {
        ArrayList> rst = new ArrayList>();
        if (root == null)
            return rst;
        Queue queue = new LinkedList ();
        queue.offer(root);
        
        while (!queue.isEmpty())
        {
            ArrayList level = new ArrayList();
            int size = queue.size();
            for (int i = 0; i < size; i++)
            {
                TreeNode tmp = queue.poll();
                level.add(tmp.val);
                if (tmp.left != null)
                    queue.add(tmp.left);
                if (tmp.right != null)
                    queue.add(tmp.right);
            }
            rst.add(level);
        }
        return rst;
    }
}

Zigzag Level Order

Update 2015 - 03 - 05:
A cleaner version:

public List> zigzagLevelOrder(TreeNode root) {
        List> rst = new ArrayList>();
        if(root == null)
            return rst;
        Stack currLevel = new Stack();
        currLevel.push(root);
        boolean reverse = true;
        while(!currLevel.isEmpty()){
            Stack nextLevel = new Stack();
            List level = new ArrayList();
            while(!currLevel.isEmpty()){
                TreeNode curr = currLevel.pop();
                if(reverse){
                    if(curr.left != null) nextLevel.push(curr.left);
                    if(curr.right != null)  nextLevel.push(curr.right);
                }
                else{
                    if(curr.right != null) nextLevel.push(curr.right);
                    if(curr.left != null) nextLevel.push(curr.left);
                }
                level.add(curr.val);
            }
            rst.add(level);
            currLevel = nextLevel;
            reverse = !reverse;
        }
        return rst;
        
    }

Update: 2015 - 01 - 05:
Theoretically for an easy problem like this, I should not make any mistakes. Yet I do. The tricky part is that
1. Unlike Level Order Traversal, we cannot use Queue, since we need to keep switching the order to add elements. We use a Stack. The it comes
2. The Stack works in a way that the last element that is added will be popped out first, so if we only use one Stack, we end up popping out next level nodes before all the current level nodes are popped out.
3. When dealing with two Stacks, we need to deal with the copy problem. Since Java passes everything by value, and when it comes to objects, it passes a copy of the reference from one object to another. So since we need to "clear" nextLevel stack and add new elements, we need to initialize a new nextLevel Stack: giving it a new memory address. Read this if you are confused about passing values in Java.

public class Solution {
    public ArrayList> zigzagLevelOrder(TreeNode root) {
        ArrayList> rst = new ArrayList>();
        if (root == null)
            return rst;
        Stack currentLevel = new Stack ();
        Stack nextLevel = new Stack ();
        boolean isNormal = false;
        currentLevel.push(root);
        while (!currentLevel.isEmpty())
        {
            ArrayList level = new ArrayList();
            int size = currentLevel.size();
            for (int i = 0; i < size; i++)
            {
                 TreeNode tmp = currentLevel.pop();
                 level.add(tmp.val);
                 if (isNormal)
                 {
                    if (tmp.right != null)
                        nextLevel.add(tmp.right);
                    if (tmp.left != null)
                        nextLevel.add(tmp.left);
                 }
                 else
                 {
                    if (tmp.left != null)
                        nextLevel.add(tmp.left);
                    if (tmp.right != null)
                        nextLevel.add(tmp.right);
                 }
            }
            rst.add(level);
            currentLevel = nextLevel;
            nextLevel = new Stack();
            isNormal = !isNormal;
        }
        return rst;
    }
}