// Runtime: 59 ms, faster than 32.73% of Java online submissions for Binary Search Tree Iterator.
// Memory Usage: 51 MB, less than 90.12% of Java online submissions for Binary Search Tree Iterator.
class BSTIterator {
    LinkedList<Step> steps;

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

    /** @return the next smallest number */
    public int next() {
        move();
        int result = steps.getFirst().node.val;
        return result;
    }

    private void move() {
        if (steps.isEmpty()) return;

        for (;;) {
            Step step = steps.getFirst();
            if (step.visitedLeft == false) {
                step.visitedLeft = true;
                if (step.node.left != null) {
                    steps.addFirst(new Step(step.node.left));
                    continue;
                }
            }

            if (!step.returned) {
                step.returned = true;
                break;
            }

            if (step.visitedRight == false) {
                step.visitedRight = true;
                if (step.node.right != null) {
                    steps.addFirst(new Step(step.node.right));
                    continue;
                }
            }

            steps.removeFirst();
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        for (int i = 0; i < steps.size(); i++) {
            Step step = steps.get(i);

            if (!step.visitedLeft && step.node.left != null) {
                return true;
            }
            if (!step.visitedRight && step.node.right != null) {
                return true;
            }
            if (!step.returned) {
                return true;
            }
        }
        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();
 */