public class BSTIterator {
private Stack<TreeNode> path = new Stack<TreeNode>();
public BSTIterator(TreeNode root) {
while(root!=null) {
path.push(root);
root = root.left;
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !path.isEmpty();
}
/** @return the next smallest number */
public int next() {
TreeNode node = path.pop();
if(node.right!=null) {
TreeNode curr = node.right;
while(curr!=null) {
path.push(curr);
curr = curr.left;
}
}
return node.val;
}
}
Very neat 6ms Java Solution using Stack (but can anyone help analyse the complexity?)


public class BSTIterator {
private ArrayList<Integer> list = new ArrayList<Integer>();
private int current = 0;
public BSTIterator(TreeNode root) {
inorder(root);
}private void inorder(TreeNode root){ if(root == null) return; inorder(root.left); list.add(root.val); inorder(root.right); } /** @return whether we have a next smallest number */ public boolean hasNext() { if(current < list.size()) return true; else return false; }
strong text
/** @return the next smallest number */ public int next() { return list.get(current++); }
}
Blockquote

I did exactly the same solution (well, it's the class iterative algorithm), only moved that
while
loop into a separate helper method.I believe that the complexity is all right. Spacewise it's obvious because the maximum stack size is bounded by exactly the height of the tree.
Timewise it's a bit more tricky, but let's take a closer look. If we don't enter that while loop, then
next()
is instant. That's OK. If we enter the loop and suppose it runs for M iterations. This may look not very good, but on each iteration we push an element to the stack, right? And these elements are always used by laternext()
calls. That means the sum of those Ms is equal to the total number of elements in the tree, say, N. But then the total number of calls tonext()
is also N, so when we divide those summed extra costs by N we get average of 1 per one call. This is no big surprise since the number of "pushes" is equal to the number of "pops". So the average complexity is one push and one pop per call.