Binary Tree Postorder Traversal - Iterative

Traversal problems are not that easy when recursion is not allowed. 

Given a tree:  

      1

   /     \

  2      3

 /  \    /  \

4   5 6   7

using a Stack to save traversed nodes. 

1 -> 2 -> 4 -> pop (4) -> 2 -> 5 -> pop (5) -> 2 -> pop (2) -> 1 -> 3 -> 6 -> pop (6) -> 3 -> 7 -> pop (7) -> 3 -> pop (3) -> 1 -> pop(1)

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
 
public class PostOrder {
    public ArrayList postorderTraversal(TreeNode root) {
        ArrayList rst = new ArrayList();
        if (root == null)
            return rst;
        Stack stack = new Stack();
        TreeNode prev = null;
        TreeNode curr = root;
        
        stack.push(root);
        while (!stack.empty())
        {
            curr = stack.peek();
            //Traverse down the tree: prev == null, root; left child; right child
            if (prev == null || prev.left == curr || prev.right == curr)
            {
                if (curr.left != null)
                    stack.push(curr.left);
                else if (curr.right != null) //Traverse one branch a time
                    stack.push(curr.right);
            }
            // Going up
            else if (curr.left == prev)
            {
                //Traverse the right branch
                if (curr.right != null)
                    stack.add(curr.right);
            }
            else
            {
                rst.add(curr.val);
                stack.pop();
            }
            prev = curr;
        }
        return rst;
    
    }
}