Solution: Right Child First

The plan is to keep a stack of the nodes we still have to visit. Push the root to start. Then, as long as the stack is not empty, pop a node, record its value, and push its children so the loop will reach them later.

The question is which child to push first. A first guess is to push them the way we read them, left then right:

public static <T> List<T> preOrder(Node<T> root) {
  List<T> result = new ArrayList<>();
  if (root == null) {
    return result;
  }
  Stack<Node<T>> stack = new LinkedStack<>();
  stack.push(root);
  while (!stack.isEmpty()) {
    Node<T> node = stack.top();
    stack.pop();
    result.add(node.value);
    if (node.left != null) {
      stack.push(node.left);   // push left...
    }
    if (node.right != null) {
      stack.push(node.right);  // ...then right
    }
  }
  return result;
}

Run it on this tree and watch the first couple of steps.

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

We push 5, then pop it and record it. Its children go on next, left first: 8, then 2. But a stack is last-in-first-out, and 2 was pushed last, so 2 sits on top:

┌───┐
│ 2 │ ◀── top
├───┤
│ 8 │
└───┘

The next pop takes 2, not 8, so the output begins 5 2 …. The right subtree comes before the left, which is not pre-order.

The stack reverses the order of our pushes, so push the right child first and the left child second:

    if (node.right != null) {
      stack.push(node.right);  // push right first...
    }
    if (node.left != null) {
      stack.push(node.left);   // ...so left ends up on top
    }

Now trace the whole run. Each box shows the nodes still waiting on the stack, and each step gives the result so far.

Push the root to start. Nothing is recorded yet:

┌───┐
│ 5 │ ◀── top
└───┘

Pop 5 and record it. Push its children right first, then left, so 8 ends up on top of 2. Result so far: 5.

┌───┐
│ 8 │ ◀── top
├───┤
│ 2 │
└───┘

Pop 8 and record it. Push 1, then 9. Result so far: 5 8.

┌───┐
│ 9 │ ◀── top
├───┤
│ 1 │
├───┤
│ 2 │
└───┘

Pop 9 and record it. Push its only child, 6. Result so far: 5 8 9.

┌───┐
│ 6 │ ◀── top
├───┤
│ 1 │
├───┤
│ 2 │
└───┘

Pop 6 and record it. It is a leaf, so nothing is pushed. Result so far: 5 8 9 6.

┌───┐
│ 1 │ ◀── top
├───┤
│ 2 │
└───┘

Pop 1 and record it. Also a leaf. Result so far: 5 8 9 6 1.

┌───┐
│ 2 │ ◀── top
└───┘

Pop 2 and record it. Push 7, then 4. Result so far: 5 8 9 6 1 2.

┌───┐
│ 4 │ ◀── top
├───┤
│ 7 │
└───┘

Pop 4 and record it. A leaf. Result so far: 5 8 9 6 1 2 4.

┌───┐
│ 7 │ ◀── top
└───┘

Pop 7 and record it. Push its only child, 3. Result so far: 5 8 9 6 1 2 4 7.

┌───┐
│ 3 │ ◀── top
└───┘

Pop 3 and record it. A leaf, and the stack is now empty, so the loop ends. The result is 5 8 9 6 1 2 4 7 3, the pre-order of the tree.

(empty stack)

Look at 2 in the trace. It waited at the bottom of the stack while everything under 8 was handled. That is the job the call stack did in the recursive version, where the call on 5 held on to its right subtree until the left subtree was finished.