# 0173. Binary Search Tree Iterator
###### tags: `Leetcode` `Medium` `FaceBook` `Tree Traversal` `Iterator`
Link: https://leetcode.com/problems/binary-search-tree-iterator/
## 思路
### 思路一
不用Recursion，用stack
题目描述给的很清晰 按照它说的一个一个function实现就可以了
### 思路二
inorder Traversal记录每个node的值
## Code
### 思路一

class BSTIterator {
    
    Stack<TreeNode> stack;
    
    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        leftMostIterator(root);
    }
    
    public void leftMostIterator(TreeNode root){
        while(root!=null){
            stack.push(root);
            root = root.left;
        }
    }
    
    public int next() {
        TreeNode curr = stack.pop();
        leftMostIterator(curr.right);
        return curr.val;
    }
    
    public boolean hasNext() {
        if(!stack.isEmpty()){
            return true;
        }
        return false;
    }
}

### 思路二
Time complexity : O(N) is the time taken by the constructor for the iterator.
next() would take O(1)
hasNext() would take O(1)
Space complexity : O(N) since we create a new array to contain all the nodes of the BST.

class BSTIterator {
    
    List<Integer> l;
    int idx;
    public BSTIterator(TreeNode root) {
        idx = 0;
        l = new ArrayList<>();
        inOrderTraversal(root);
    }
    
    public void inOrderTraversal(TreeNode root){
        if(root==null) return;
        inOrderTraversal(root.left);
        l.add(root.val);
        inOrderTraversal(root.right);
    }
    public int next() {
        return l.get(idx++);
    }
    
    public boolean hasNext() {
        if(idx < l.size()){
            return true;
        }
        return false;
    }
}