## Algorithm

Problem Name: 173. Binary Search Tree Iterator

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 1:

```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, 105]`.
• `0 <= Node.val <= 106`
• At most `105` calls will be made to `hasNext`, and `next`.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
struct BSTIterator {
struct TreeNode **stack;
int sp;
};
​
int depth(struct TreeNode *node) {
int l, r;
if (!node) return 0;
l = depth(node->left) + 1;
r = depth(node->right) + 1;
if (l > r) return l;
return r;
}
void push_left(struct BSTIterator *obj, struct TreeNode *node) {
do {
obj->stack[obj->sp ++] = node;
node = node->left;
} while (node);
}
struct BSTIterator *bstIteratorCreate(struct TreeNode *root) {
struct BSTIterator *obj;
int d = depth(root);

obj = calloc(1, sizeof(*obj));
//assert(obj);
if (d) {
obj->stack = malloc(d * sizeof(struct TreeNode *));
//assert(obj->stack);
push_left(obj, root);
}

return obj;
}
​
/** @return whether we have a next smallest number */
bool bstIteratorHasNext(struct BSTIterator *iter) {
return (iter->sp) ? true : false;
}
​
/** @return the next smallest number */
int bstIteratorNext(struct BSTIterator *iter) {
struct TreeNode *node;

node = iter->stack[-- iter->sp];
if (node->right) push_left(iter, node->right);

return node->val;
}
​
/** Deallocates memory previously allocated for the iterator */
void bstIteratorFree(struct BSTIterator *iter) {
if (iter->stack) free(iter->stack);
free(iter);
}
``````
Copy The Code &

Input

cmd
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]

Output

cmd
[null, 3, 7, true, 9, true, 15, true, 20, false]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

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

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

/** @return the next smallest number */
int next() {
int n = s.top();
s.pop();
return n;
}

private:
stack < int>s;

if(!root) return;
s.push(root->val);
}
};
``````
Copy The Code &

Input

cmd
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]

Output

cmd
[null, 3, 7, true, 9, true, 15, true, 20, false]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const BSTIterator = function(root) {
this.root = root;
this.stack = [];
};

/**
* @return the next smallest number
* @return {number}
*/
BSTIterator.prototype.next = function() {
while (this.root) {
this.stack.push(this.root);
this.root = this.root.left;
}
this.root = this.stack.pop();
const result = this.root.val;
this.root = this.root.right;
return result;
};

/**
* @return whether we have a next smallest number
* @return {boolean}
*/
BSTIterator.prototype.hasNext = function() {
return this.root || this.stack.length;
};
``````
Copy The Code &

Input

cmd
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]

Output

cmd
[null, 3, 7, true, 9, true, 15, true, 20, false]

### #5 Code Example with Python Programming

```Code - Python Programming```

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

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

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

def pushAll(self, node):
while node != None:
self.stack += (node,)
node = node.left
``````
Copy The Code &

Input

cmd
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]

Output

cmd
[null, 3, 7, true, 9, true, 15, true, 20, false]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _0173_BinarySearchTreeIterator
{
private readonly Stack < TreeNode> stack;

public _0173_BinarySearchTreeIterator(TreeNode root)
{
stack = new Stack();
LeftMostInorder(root);
}

private void LeftMostInorder(TreeNode root)
{
while (root != null)
{
stack.Push(root);
root = root.left;
}
}

/** @return the next smallest number */
public int Next()
{
var node = stack.Pop();

if (node.right != null)
LeftMostInorder(node.right);

return node.val;
}

/** @return whether we have a next smallest number */
public bool HasNext()
{
return stack.Count > 0;
}
}
}
``````
Copy The Code &

Input

cmd
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]

Output

cmd
[null, 3, 7, true, 9, true, 15, true, 20, false]