Problem: Iterative Post-order Traversal

Pre-order records a node as soon as it pops the node from the stack. In-order records a node only after its left subtree. Post-order records a node only after both of its subtrees.

public static <T> List<T> postOrder(Node<T> root) {

}

Example 1:

       ╭───╮
       │ 1 │
       ╰─┬─╯
    ┌────┴────┐
  ╭─┴─╮     ╭─┴─╮
  │ 2 │     │ 3 │
  ╰─┬─╯     ╰───╯
  ┌─┘
╭─┴─╮
│ 4 │
╰───╯

This is the tree from the pre-order problem. The result is [4, 2, 3, 1].

Example 2:

An empty tree, where root is null, returns [].

For reference, here is the recursive post-order traversal:

private static <T> void postOrder(Node<T> node, List<T> result) {
  if (node == null) {
    return;
  }
  postOrder(node.left, result);
  postOrder(node.right, result);
  result.add(node.value);
}

Try it before reading on.