---
# System prepended metadata

title: 173. Binary Search Tree Iterator
tags: [bst, leetcode, medium]

---


# 173. Binary Search Tree Iterator

###### tags: `leetcode`,`bst`,`medium`



[morris traversal](/tvUPX5ubQtqHWys0LQADsQ)
>ref: https://leetcode.com/problems/binary-search-tree-iterator/
>
![](https://i.imgur.com/T0QExio.png)

![](https://i.imgur.com/px7dVQk.png)
![](https://i.imgur.com/3kfIeKv.png)


![](https://i.imgur.com/CKnBYiQ.png)




>1. loop一次 bst用QUEUE存 需查找一次再找尋 O(N+K) K為BST inorder位置
>2. 空間需要o(n)

```java=
    Queue<Integer> arr;
    
    int size;
    
    int pointer;

    public BSTIterator(TreeNode root) {
        arr=new LinkedList<>();
        size=0;
        pointer=-1;
        traverse(root);
    }
    
    public int next() {
        pointer++;
        if(arr.peek()!=null){
            return arr.poll();
        }
        return -1;
    }
    
    public boolean hasNext() {
        return arr.peek()!=null;
    }
    
    private void traverse(TreeNode root){
        
        if(root==null)return;
        traverse(root.left);
        arr.offer(root.val);
        size++;
        traverse(root.right);
        
    }
```

---


    
    
    
