# 173. Binary Search Tree Iterator

Implement the `BSTIterator` class that represents an iterator over the [**in-order traversal**](https://en.wikipedia.org/wiki/Tree_traversal#In-order_\(LNR\)) 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:**

![](https://assets.leetcode.com/uploads/2018/12/25/bst-tree.png)

<pre><code><strong>Input
</strong>["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
<strong>Output
</strong>[null, 3, 7, true, 9, true, 15, true, 20, false]

<strong>Explanation
</strong>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
</code></pre>

&#x20;

**Constraints:**

* The number of nodes in the tree is in the range `[1, 10`<sup>`5`</sup>`]`.
* `0 <= Node.val <= 10`<sup>`6`</sup>
* At most `10`<sup>`5`</sup> calls will be made to `hasNext`, and `next`.

&#x20;

**Follow up:**

* Could you implement `next()` and `hasNext()` to run in average `O(1)` time and use `O(h)` memory, where `h` is the height of the tree?

分析

### ✅思路（Lazy 中序遍历）

中序遍历 BST 的顺序是：左 → 根 → 右。\
我们用一个栈模拟这个过程，并**只存一条路径**：

#### ✅初始化时：

* 一路往左压栈，把最小的元素放到栈顶

#### ✅每次调用 `next()`：

* 弹出栈顶元素（当前最小）
* 然后如果这个节点有右子树，把它的右子树的左边一条路径压栈

```python3
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        self.current = root

    def next(self) -> int:
        while self.current:
            self.stack.append(self.current)
            self.current = self.current.left
        self.current = self.stack.pop()
        val = self.current.val
        self.current = self.current.right
        return val

    def hasNext(self) -> bool:
        return self.current is not None or len(self.stack) > 0

# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()
```