/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class BSTIterator {
    LinkedList<Step> steps;

    public BSTIterator(TreeNode root) {
        steps = new LinkedList<Step>();
        steps.add(new Step(root));
    }

    /** @return the next smallest number */
    public int next() {
        System.out.println("calling next");
        move();
        int result = steps.getFirst().node.val;
        System.out.println("next returned " + result);
        return result;
    }

    private void move() {
        System.out.println("calling move");
        if (steps.isEmpty()) return;

        Step step = steps.getFirst();
        if (step.visitedLeft == false) {
            System.out.println("left from " + step.node.val);
            step.visitedLeft = true;
            if (step.node.left != null) {
                steps.addFirst(new Step(step.node.left));
                move();
            }
        }

        if (!step.returned) {
            System.out.println("return " + step.node.val);
            step.returned = true;
            return;
        }

        if (step.visitedRight == false) {
            System.out.println("right from " + step.node.val);
            step.visitedRight = true;
            if (step.node.right != null) {
                steps.addFirst(new Step(step.node.right));
                move();
            }
        }

        System.out.println("go up");
        steps.removeFirst();
        move();
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        System.out.println("calling hasNext");
        for (int i = 0; i < steps.size(); i++) {
            Step step = steps.get(i);
            if (!step.visitedLeft || !step.visitedRight || !step.returned) {
                System.out.println("hasNext: true");
                return true;
            }
        }
        System.out.println("hasNext: false");
        return false;
    }

    class Step {
        TreeNode node;
        boolean visitedLeft;
        boolean visitedRight;
        boolean returned;
        public Step(TreeNode node ) {
            this.node = node;
        }
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */