Problem: Iterative In-order Traversal

In pre-order we record a node as soon as we reach it. In-order is harder. We can record a node only after its whole left subtree has been traversed, so reaching a node is not enough to record it.

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

}

Example 1:

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

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

Example 2:

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

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

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

The hard part is knowing, when we pop a node from a stack, whether its left subtree has been visited yet. Try it before reading on.