Solution: Pre-order in Reverse

Take the pre-order solution unchanged: push the root, pop a node, record it, and push its children. Every parent then comes out ahead of its children. Here is the tree again:

                  ╭───╮
                  │ 5 │
                  ╰─┬─╯
         ┌──────────┴──────────┐
       ╭─┴─╮                 ╭─┴─╮
       │ 8 │                 │ 2 │
       ╰─┬─╯                 ╰─┬─╯
    ┌────┴────┐           ┌────┴────┐
  ╭─┴─╮     ╭─┴─╮       ╭─┴─╮     ╭─┴─╮
  │ 9 │     │ 1 │       │ 4 │     │ 7 │
  ╰─┬─╯     ╰───╯       ╰───╯     ╰─┬─╯
  ┌─┘                               └─┐
╭─┴─╮                               ╭─┴─╮
│ 6 │                               │ 3 │
╰───╯                               ╰───╯

On this tree the output begins 5 8. For post-order, that is backwards: a parent should come after its children, not before. The reverse of that sequence puts every node after its descendants, which is what post-order needs.

We have to get the left and right subtrees in the correct order too. Post-order wants the left subtree before the right. Since we reverse the sequence at the end, the sequence before reversing needs the right subtree before the left. So we want to pop the node, then its right subtree, then its left subtree. To get that, we push the left child first and the right child second, so the right child comes off the stack first. That is the opposite of the push order we used for pre-order.

Recording node, then right, then left as we pop gives the sequence 5 2 7 3 4 8 1 9 6. Read it backwards: 6 9 1 8 4 3 7 2 5, which is exactly the post-order.

To reverse that sequence we use a second stack. As each node comes off the working stack, we push it onto an output stack instead of recording it straight away. A stack returns its items in the reverse of the order they went in, so once the working stack is empty we pop the output stack into the result and the values come out in post-order:

public static <T> List<T> postOrder(Node<T> root) {
  List<T> result = new ArrayList<>();
  if (root == null) {
    return result;
  }
  Stack<Node<T>> stack = new LinkedStack<>();
  Stack<Node<T>> output = new LinkedStack<>();
  stack.push(root);
  while (!stack.isEmpty()) {
    Node<T> node = stack.top();
    stack.pop();
    output.push(node);             // record onto the second stack
    if (node.left != null) {
      stack.push(node.left);       // push left first...
    }
    if (node.right != null) {
      stack.push(node.right);      // ...then right, so right comes off first
    }
  }
  while (!output.isEmpty()) {       // drain the output stack into the result
    result.add(output.top().value);
    output.pop();
  }
  return result;
}

On our tree, the first loop pushes the nodes onto the output stack in the order 5 2 7 3 4 8 1 9 6, the sequence we worked out above. The second loop pops them off in reverse, 6 9 1 8 4 3 7 2 5, which is the post-order. So iterative post-order is pre-order with the push order swapped and the output reversed by a second stack.