# 173. Binary Search Tree Iterator

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

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



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

    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);
        
    }

---