Solution: Following the Left Spine

A node is not ready to record until its left subtree is done. One way to handle this: when we pop a node that has a left child, put the node back on the stack and push its left child on top of it, so its left subtree is handled before we return to the node:

Stack<Node<T>> stack = new LinkedStack<>();
stack.push(root);
while (!stack.isEmpty()) {
  Node<T> node = stack.top();
  stack.pop();
  if (node.left != null) {
    stack.push(node);        // not ready yet — keep it for later
    stack.push(node.left);   // visit its left subtree first
  } else {
    result.add(node.value);  // no left subtree, record now
  }
}

If we trace it on this tree, it fails.

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

We push 5, pop it, and since it has a left child we push 5 back and then 8. We pop 8, push 8 back and 9. We pop 9, push 9 back and 6. We pop 6; it has no left child, so we record it. After recording 6, the stack reads 9 8 5 from the top:

┌───┐
│ 9 │ ◀── top
├───┤
│ 8 │
├───┤
│ 5 │
└───┘

We pop 9, see it has a left child, and push 9 back with 6 on top. This is the same stack we had before we popped 6:

┌───┐
│ 6 │ ◀── top
├───┤
│ 9 │
├───┤
│ 8 │
├───┤
│ 5 │
└───┘

The value node.left never changes, so nothing tells us that 9’s left subtree is already done, and the loop runs forever. We could keep a set of visited nodes, but there is a way that needs no extra bookkeeping.

The fix is to arrange the stack so that a node’s left subtree is always done by the time we pop the node. Then we do not need to check it at each pop. Before popping anything, follow the current node down its left edges as far as they go, and push every node along the way. This path of left edges is called the left spine. When you cannot go left any further, the node on top of the stack has no unvisited left subtree, so it is ready: pop it, record it, then step into its right child and follow that subtree’s left spine the same way.

public static <T> List<T> inOrder(Node<T> root) {
  List<T> result = new ArrayList<>();
  Stack<Node<T>> stack = new LinkedStack<>();
  Node<T> current = root;
  while (current != null || !stack.isEmpty()) {
    while (current != null) {   // follow the left spine, pushing as we go
      stack.push(current);
      current = current.left;
    }
    current = stack.top();      // the top has no unvisited left — it is ready
    stack.pop();
    result.add(current.value);  // record it
    current = current.right;    // then move into its right subtree
  }
  return result;
}

An empty tree needs no special case. When root is null, current is null and the stack is empty, so the loop never runs and the method returns an empty list.

Follow the left spine from 5, pushing 5, 8, 9, 6. Nothing is recorded yet:

┌───┐
│ 6 │ ◀── top
├───┤
│ 9 │
├───┤
│ 8 │
├───┤
│ 5 │
└───┘

Pop 6 and record it. It has no right child. Result so far: 6.

┌───┐
│ 9 │ ◀── top
├───┤
│ 8 │
├───┤
│ 5 │
└───┘

Pop 9 and record it. It has no right child. Result so far: 6 9.

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

Pop 8 and record it. Its right child is 1. Result so far: 6 9 8.

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

Follow the left spine from 1, pushing 1.

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

Pop 1 and record it. It has no right child. Result so far: 6 9 8 1.

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

Pop 5 and record it. Its right child is 2. Result so far: 6 9 8 1 5. The stack is now empty, but current is 2, so the loop keeps going.

(empty stack)

Follow the left spine from 2, pushing 2, 4.

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

Pop 4 and record it. It has no right child. Result so far: 6 9 8 1 5 4.

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

Pop 2 and record it. Its right child is 7. Result so far: 6 9 8 1 5 4 2.

(empty stack)

Follow the left spine from 7, pushing 7.

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

Pop 7 and record it. Its right child is 3. Result so far: 6 9 8 1 5 4 2 7.

(empty stack)

Follow the left spine from 3, pushing 3.

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

Pop 3 and record it. It has no right child, so current is null, and with the stack also empty, the loop ends. The result is 6 9 8 1 5 4 2 7 3, the in-order traversal of the tree.

(empty stack)

At any point, the stack holds the ancestors of the current node whose left subtree we are still inside. The deepest one is on top.