> For the complete documentation index, see [llms.txt](https://shangan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shangan.gitbook.io/algorithm/he-xin-suan-fa-200-ti/untitled-2/binary-search-tree-iterator.md).

# Binary Search Tree Iterator

* LeetCode版

{% tabs %}
{% tab title="Java" %}

```java
public class BSTIterator {
    
    private Stack<TreeNode> stack = new Stack<>();

    public BSTIterator(TreeNode root) {
        TreeNode cur = root;
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    public int next() {
        TreeNode ans = stack.pop();
        TreeNode cur = ans.right;
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        return ans.val;
    }
}
```

{% endtab %}
{% endtabs %}

* LintCode版

{% tabs %}
{% tab title="Java" %}

```java
public class BSTIterator {
    
    private Stack<TreeNode> stack = new Stack<>();

    public BSTIterator(TreeNode root) {
        TreeNode cur = root;
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    public TreeNode next() {
        TreeNode ans = stack.pop();
        TreeNode cur = ans.right;
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        return ans;
    }
}
```

{% endtab %}
{% endtabs %}

![](https://2784211123-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M-ELB26IpzCEJWSDi0m%2F-M-ELbsic2B8wwsarT-C%2F-M-EMqc6UhBUlpM3zyHy%2F1580805867266.jpg?alt=media\&token=11a20b67-9e32-4c02-bf02-c405dac8ef0f)