> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/101-200/binary-search-tree-iterator.md).
# 173. Binary Search Tree Iterator
### Description
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling `next()` will return the next smallest number in the BST.
**Note:**
* `next()` and `hasNext()` should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
* You may assume that `next()` call will always be valid, that is, there will be at least a next smallest number in the BST when `next()` is called.
### Constraints
### Approach
### Links
* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/binary-search-tree-iterator/)
* [ProgramCreek](https://www.programcreek.com/2014/04/leetcode-binary-search-tree-iterator-java/)
* YouTube
### **Examples**
{% tabs %}
{% tab title="Example 1" %}
**Input:**
\["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext
\[\[\[7, 3, 15, null, null, 9, 20]], \[null], \[null], \[null], \[null], \[null], \[null], \[null], \[null], \[null]]
**Output:**
\[null, 3, 7, true, 9, true, 15, true, 20, false]
**Explanation:**
{% endtab %}
{% endtabs %}
### **Solutions**
{% tabs %}
{% tab title="Solution 1" %}
```java
/**
* Time complexity :
* Space complexity :
*/
/**
* Your BSTIterator object will be instantiated and called as such:
* BSTIterator obj = new BSTIterator(root);
* int param_1 = obj.next();
* boolean param_2 = obj.hasNext();
*/
class BSTIterator {
private Stack stack;
public BSTIterator(TreeNode root) {
stack = new Stack();
pushNodes(root);
}
/** @return the next smallest number */
public int next() {
TreeNode root = stack.pop();
pushNodes(root.right);
return root.val;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
}
private void pushNodes(TreeNode root) {
while(root != null) {
stack.push(root);
root = root.left;
}
}
}
```
{% endtab %}
{% endtabs %}
### **Follow up**
*
