Java Solution with O(1) time and O(h) space complexities ON AVERAGE

• Below is the java solution.
At the first glance, the algorithm run in O(h) time & O(h) space. But if you take a closer look at the problem, you will see that it asks for "on average".
We see that, for the function next, each node is popped on to the stack exactly 1 time. Hence, on average, it is O(1) time complexity.

``````import java.util.Stack;

public class BSTIterator {

private Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new Stack<TreeNode>();
TreeNode tempNode = root;
if(root!=null) {
while(tempNode != null){
stack.push(tempNode);
tempNode = tempNode.left;
}
}
}

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

/** @return the next smallest number */
public int next() {
TreeNode node = stack.pop();
TreeNode tempNode = node.right;
if(tempNode!=null){
while(tempNode!=null){
stack.push(tempNode);
tempNode = tempNode.left;
}
}
return node.val;
}
}``````

• ``````My Java code, same idea with above.

public class BSTIterator {
Stack<TreeNode> s = new Stack<TreeNode>();
public BSTIterator(TreeNode root) {
findMin(root);
}

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

/** @return the next smallest number */
public int next() {
TreeNode nextMin = s.pop();
findMin(nextMin.right);

return nextMin.val;
}

private void findMin(TreeNode n) {
while(n != null) {
s.push(n);
n = n.left;
}
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.