# LeetCode: 173. Binary Search Tree Iterator

**The Problem**

Implement the `BSTIterator`

class that represents an iterator over the ** in-order traversal** of a binary search tree (BST):

`BSTIterator(TreeNode root)`

Initializes an object of the`BSTIterator`

class. The`root`

of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.`boolean hasNext()`

Returns`true`

if there exists a number in the traversal to the right of the pointer, otherwise returns`false`

.`int next()`

Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to `next()`

will return the smallest element in the BST.

You may assume that `next()`

calls will always be valid. That is, there will be at least a next number in the in-order traversal when `next()`

is called.

**Example**

```
Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]
Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // return 3
bSTIterator.next(); // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 20
bSTIterator.hasNext(); // return False
```

**Constraints:**

- The number of nodes in the tree is in the range
`[1, 10`

.^{5}] `0 <= Node.val <= 10`

^{6}- At most
`10`

calls will be made to^{5}`hasNext`

, and`next`

.

**Solution**

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

```
class BSTIterator {
queue<int> nodes;
public:
BSTIterator(TreeNode* root) {
nodes.push(-1);
fillNodes(root);
}
int next() {
nodes.pop();
return nodes.front();
}
bool hasNext() {
return nodes.size() > 1;
}
void fillNodes(TreeNode* root) {
if (root == NULL) return;
fillNodes(root->left);
nodes.push(root->val);
fillNodes(root->right);
}
};
```

Let's break down this code step by step:

1. `class BSTIterator {`

: This line declares the start of a class definition named `BSTIterator`

. This class will be responsible for iterating through the BST.

2. `queue<int> nodes;`

: It declares a queue named `nodes`

. In this queue, we will store the values of the BST nodes in in-order.

3. `BSTIterator(TreeNode* root) {`

: This is the constructor of the `BSTIterator`

class. It takes a pointer to the root of the BST as an argument.

`nodes.push(-1);`

: to initialized to a non-existent number smaller than any element in the BST`fillNodes(root);`

: It then calls the`fillNodes`

function to populate the`nodes`

queue with values from the BST.

4. `int next() {`

: used to get the next value in the BST.

`nodes.pop();`

: It removes the first element from the`nodes`

queue.`return nodes.front();`

: It returns the new front element of the queue, which will be the next smallest value in the BST.

5. `bool hasNext() {`

: This is a member function named `hasNext`

. It checks if there are more elements to iterate over.

`return nodes.size() > 1;`

: It returns`true`

if the size of the`nodes`

queue is greater than 1, meaning there are more elements to iterate. The extra`-1`

placeholder ensures this condition works correctly.

5. `void fillNodes(TreeNode* root) {`

: This is a member function named `fillNodes`

. It recursively populates the `nodes`

queue with BST values.

`if (root == NULL) return;`

: If the current node is NULL (empty), it returns and does nothing.`fillNodes(root->left);`

: It recursively calls`fillNodes`

on the left subtree of the current node.`nodes.push(root->val);`

: It pushes the value of the current node into the`nodes`

queue. This is where the values are sorted in ascending order.`fillNodes(root->right);`

: It recursively calls`fillNodes`

on the right subtree of the current node.