Interview Question for Software Engineer at Google:

import java.util.*;

public class TreeIterator<T> {

    // In-order iterator for a binary tree (untested)

    private Stack<TreeNode<T>> s;

    public TreeIterator(TreeNode<T> root) {
        s = new Stack<TreeNode<T>>();
        s.push(root);
        setNext();
    }

    public boolean hasNext() {
        return s.peek() != null;
    }

    public TreeNode<T> next() throws Exception {

        if (!hasNext())
            throw new Exception("No next");

        // Next is node at the top of the stack
        TreeNode<T> next = s.pop();

        // If the node had right child push that
        // then all children to left
        TreeNode<T> right = next.getrChild();
        if (right != null) {
            s.push(right);
            setNext();
        }
        return next;
    }

    private void setNext() {
        // push while there are left children
        TreeNode<T> cur = s.peek();
        while (cur != null) {
            TreeNode<T> left = cur.getlChild();
            if (left != null)
                s.push(left);
            cur = left;
        }
    }
}