# Java solution using both stack and recursion with explanation

• ``````public class BSTIterator {
private Queue<Integer> queue;

public BSTIterator(TreeNode root) {
queue = inorderTraversal(root);
//Enable following two lines if using recursion.
//inorder(root,queue);
}

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

/** @return the next smallest number */
public int next() {
if(!queue.isEmpty()) {
return queue.poll();
}
return -1;
}

private void inorder(TreeNode root, Queue<Integer> q) {
if(root==null) {
return;
}
inorder(root.left,q);
inorder(root.right,q);
}

private Queue<Integer> inorderTraversal(TreeNode root) {
if(root==null) {
return list;
}
Stack<TreeNode> stack = new Stack<>();
while(root!=null) {
stack.push(root);
root=root.left;
}

while(!stack.isEmpty()) {
TreeNode temp = stack.pop();
System.out.println(temp.val);
TreeNode right = temp.right;
if(right!=null) {
stack.push(right);
TreeNode left = right.left;
while(left!=null) {
stack.push(left);
left = left.left;
}
}
}
return list;
}
}
``````

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