BSTIterator.java

import java.util.Stack;

public class BSTIterator {
 // Definition for binary tree
 public class TreeNode {
 int val;
 TreeNode left;
 TreeNode right;
 TreeNode(int x) { val = x; }
 }

 Stack<TreeNode> stack;

 public BSTIterator(TreeNode root) {
 stack = new Stack<TreeNode>();
 pushAll(root);
 }

 /** @return whether we have a next smallest number */
 public boolean hasNext() {
 return !stack.empty();
 }

 /** @return the next smallest number */
 public int next() {
 TreeNode smlestNode = stack.pop();
 pushAll(smlestNode.right);
 return smlestNode.val;
 }

 public void pushAll(TreeNode node) {
 for(; node != null; stack.push(node), node = node.left);
 }
}

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */