Problem: Iterative Pre-order Traversal

Start with pre-order, the easiest of the three.

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

}

Example 1:

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

The result is [1, 2, 4, 3].

Example 2:

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

Here is the recursive pre-order from the chapter, changed to add each value to a list instead of printing it:

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

In this recursive version, the call stack keeps track of the right subtree at each node while the left subtree is being worked through. Replace the call stack with a Stack<Node<T>> that holds the nodes still to be visited. Try it before reading on.