## Approach 1: Recursive

• Time:Constructor: O(n), next(): O(1), hasNext(): O(1)
• Space:O(n)

## C++

``````class BSTIterator {
public:
BSTIterator(TreeNode* root) {
inorder(root);
}

/** @return the next smallest number */
int next() {
return vals[i++];
}

/** @return whether we have a next smallest number */
bool hasNext() {
return i < vals.size();
}

private:
int i = 0;
vector<int> vals;

void inorder(TreeNode* root) {
if (!root)
return;

inorder(root->left);
vals.push_back(root->val);
inorder(root->right);
}
};
``````

## JAVA

``````class BSTIterator {
public BSTIterator(TreeNode root) {
inorder(root);
}

/** @return the next smallest number */
public int next() {
return vals.get(i++);
}

/** @return whether we have a next smallest number */
public boolean hasNext() {
return i < vals.size();
}

private int i = 0;
private List<Integer> vals = new ArrayList<>();

private void inorder(TreeNode root) {
if (root == null)
return;

inorder(root.left);
inorder(root.right);
}
}
``````

## Python

``````class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.stack = []
self.pushLeftsUntilNone(root)

def next(self) -> int:
root = self.stack.pop()
self.pushLeftsUntilNone(root.right)
return root.val

def hasNext(self) -> bool:
return self.stack

def pushLeftsUntilNone(self, root: Optional[TreeNode]):
while root:
self.stack.append(root)
root = root.left
``````

## Approach 2: Iterative

• Time:Constructor: O(h), next(): O(h), hasNext(): O(1)
• Space:O(h)

## C++

``````class BSTIterator {
public:
BSTIterator(TreeNode* root) {
pushLeftsUntilNull(root);
}

int next() {
TreeNode* root = stack.top();
stack.pop();
pushLeftsUntilNull(root->right);
return root->val;
}

bool hasNext() {
return !stack.empty();
}

private:
stack<TreeNode*> stack;

void pushLeftsUntilNull(TreeNode* root) {
while (root) {
stack.push(root);
root = root->left;
}
}
};
``````

## JAVA

``````class BSTIterator {
public BSTIterator(TreeNode root) {
pushLeftsUntilNull(root);
}

public int next() {
TreeNode root = stack.pop();
pushLeftsUntilNull(root.right);
return root.val;
}

public boolean hasNext() {
return !stack.isEmpty();
}

private Deque<TreeNode> stack = new ArrayDeque<>();

private void pushLeftsUntilNull(TreeNode root) {
while (root != null) {
stack.push(root);
root = root.left;
}
}
}
``````

## Python

``````class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.stack = []
self.pushLeftsUntilNull_(root)

def next(self) -> int:
root = self.stack.pop()
self.pushLeftsUntilNull_(root.right)
return root.val

def hasNext(self) -> bool:
return self.stack

def pushLeftsUntilNull_(self, root: Optional[TreeNode]) -> None:
while root:
self.stack.append(root)
root = root.left
``````