The In-order Iterator

Here is a binary search tree that implements Iterable<T>. Its iterator returns the tree’s values in ascending order, one value per call to next. next throws NoSuchElementException when there are no values left. The iterator is an inner class, so it can read root. Its only field is a stack of nodes, and it does not use recursion.

public class BinarySearchTree<T extends Comparable<T>>
    implements Iterable<T> {
  private Node<T> root;

  private static class Node<T> {
    T value;
    Node<T> left;
    Node<T> right;

    Node(T value) {
      this.value = value;
    }
  }

  @Override
  public Iterator<T> iterator() {
    return new BinarySearchTreeIterator();
  }

  private class BinarySearchTreeIterator implements Iterator<T> {
    private Stack<Node<T>> stack = new LinkedStack<>();

    BinarySearchTreeIterator() {
      // TODO
    }

    @Override
    public boolean hasNext() {
      // TODO
    }

    @Override
    public T next() {
      // TODO
    }
  }
}

The stack follows this interface, and LinkedStack implements it:

public interface Stack<T> {
  void push(T item);   // adds item to the top
  void pop();          // removes the top item; throws if empty
  T top();             // returns the top item; throws if empty
  boolean isEmpty();
}

private class BinarySearchTreeIterator implements Iterator<T> {
  private Stack<Node<T>> stack = new LinkedStack<>();

  BinarySearchTreeIterator() {
    pushLeftSpine(root);
  }

  private void pushLeftSpine(Node<T> node) {
    while (node != null) {
      stack.push(node);
      node = node.left;
    }
  }

  @Override
  public boolean hasNext() {
    return !stack.isEmpty();
  }

  @Override
  public T next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    Node<T> node = stack.top();
    stack.pop();
    T value = node.value;
    pushLeftSpine(node.right);
    return value;
  }
}

constructor               stack: 17 33
next returns 17           stack: 25 33
next returns 25           stack: 33
next returns 33           stack: 40 46 58
next returns 40           stack: 46 58
next returns 46           stack: 58
next returns 58           stack: 71
next returns 71           stack: (empty)