# Binary Search Tree Iterator

## Question ([LC.173](https://leetcode.com/problems/binary-search-tree-iterator/#/description))

> Implement an iterator over a binary search tree.

It will be initialized with the root node of a BST.

## Example

```
// root is the root node of BST [4,2,10,1,3,6,11]
BSTIterator iter = new BSTIterator(root);
while (iter.hasNext()) print iter.next() + ",";
// output: 1,2,3,4,6,10,11
```

## Approach

Iterative inorder traversal

## Code

```java
public class BSTIterator {
    private Stack<TreeNode> stack;
    private TreeNode current;

    /** Initialize the stack */
    public BSTIterator(TreeNode root) {
        stack = new Stack<TreeNode>();
        current = root;
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        // we are not at the bottom right of the BST
        return (!stack.isEmpty() || current != null);
    }

    /** @return the next smallest number */
    public int next() {
        int smallest;
        // left child first
        while (current != null) {
            stack.push(current);
            current = current.left;
        } 
        // backtrack to parent
        // log inorder
        current = stack.pop();
        smallest = current.val;
        // right child last
        current = current.right;
        return smallest;
    }
}
```

To some degree, each `next()` is kind of like a recursive call, given a new root and perform the in-order traversal from there.&#x20;

```python
class BSTIterator:

    def __init__(self, root: TreeNode):
        self.stack = deque()
        self.cur = root
        

    def next(self) -> int:
        # keep dumping
        while self.cur is not None:
            self.stack.append(self.cur)
            self.cur = self.cur.left
        # pop
        self.cur = self.stack.pop()
        next_val = self.cur.val
        self.cur = self.cur.right
        return next_val

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

## Reading

Traversing binary trees simply and cheaply by Joseph M. Morris


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-1/basic_data_structure/binary_tree/binary_search_tree/binary-search-tree-iterator.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.