###### tags: `Leetcode` `medium` `design` `tree` `python` `c++`

# 173. Binary Search Tree Iterator

## [題目連結:] https://leetcode.com/problems/binary-search-tree-iterator/description/

## 題目:
Implement the ```BSTIterator``` class that represents an iterator over the **in-order traversal** of a binary search tree (BST):

* ```BSTIterator(TreeNode root)``` Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
* ```boolean hasNext()``` Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
* ```int next()``` Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to ```next()``` will return the smallest element in the BST.

You may assume that ```next()``` calls will always be valid. That is, there will be at least a next number in the in-order traversal when ```next()``` is called.

**Follow up:**
* Could you implement ```next()``` and ```hasNext()``` to run in average ```O(1)``` time and use ```O(h)``` memory, where h is the height of the tree?


## 解題想法:
* 題目為實作一個關於BST的內容:
* BST為inorder traversal
* next為return當前root.val，並將其root指向inorder的下個root
* hasNext為判斷是否還能繼續遍歷

## Python Sol1:
* 因為要求 **O(h)** space : h為樹高
* def checkLeft(self,root):
* 將左子逐一加入stack中
* 因為inorder性質，要先拜訪左子
* 因此對於next時，curRoot=stack.pop() 即為解
* 再判斷curRoot是否有右子
* 有的話再進行checkLeft()
* total: O(1)

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)
        
        
class BSTIterator(object):

    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.stack=[]
        self.checkLeft(root)

    def checkLeft(self,root):
        while root:
            self.stack.append(root)
            root=root.left

    #time O(1) space:O(h) h:height of tree
    def next(self):
        """
        :rtype: int
        """
        curRoot=self.stack.pop()
        if curRoot.right:
            self.checkLeft(curRoot.right)
        return curRoot.val
        

    def hasNext(self):
        """
        :rtype: bool
        """
        return True if self.stack else False
 
if __name__=='__main__':
    root=TreeNode(7)
    root.insertLeft(3)
    root.insertRight(15)
    root.right.insertLeft(9)
    root.right.insertRight(20)
    root.printTree() #[7, 3, 15, 9, 20]

    obj = BSTIterator(root)
    param_1 = obj.next()
    print(param_1) #3
    param_2 = obj.hasNext()
    print(param_2) #True

## Python Sol2:
* 直接額外寫個函式inoder紀錄中續遍歷的結果
* 但是space為O(n): n為root總數

class BSTIterator(object):

    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.stack=[]
        self.inorder(root)
    def inorder(self,root):
        if not root:
            return
        self.inorder(root.left)
        self.stack.append(root)
        self.inorder(root.right)
        
    def next(self):
        """
        :rtype: int
        """
        ans=self.stack.pop(0)
        return ans.val

    def hasNext(self):
        """
        :rtype: bool
        """
        return True if self.stack else False

## C++ Sol1:

#include<bits/stdc++.h>
using namespace std;

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(): val(0), left(nullptr), right(nullptr){}
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

void InsertLeft(TreeNode* root, int data){
    TreeNode *tmp=root;
    if (tmp->left!=nullptr)
        InsertLeft(tmp->left,data);
    else{
        TreeNode *new_data= new TreeNode(data);
        tmp->left=new_data;
    }
}

void InsertRight(TreeNode* root, int data){
    TreeNode *tmp=root;
    if (tmp->right!=nullptr)
        InsertRight(tmp->right,data);
    else{
        TreeNode *new_data= new TreeNode(data);
        tmp->right=new_data;
    }
}

void PrintTree(TreeNode *root){
    TreeNode *tmp=root;
    queue<TreeNode*> que;
    vector<int> res;
    que.push(root);
    while (!que.empty()){
        TreeNode *root=que.front(); que.pop();
        res.push_back(root->val);
        if (root->left)
            que.push(root->left);
        if (root->right)
            que.push(root->right);
    }
    for (auto val: res){
        cout<<val<<" ";
    }
    cout<<endl;
}

class BSTIterator {
public:
    BSTIterator(TreeNode* root) {
        checkLeft(root);
    }

    void checkLeft(TreeNode* root){
        while (root){
            res.push(root);
            root=root->left;
        }
    }

    int next() {
        TreeNode *curRoot=res.top(); res.pop();
        if (curRoot->right)
            checkLeft(curRoot->right);
        return curRoot->val;
    }

    bool hasNext() {
        return !res.empty() ? true:false;
    }

private:
    stack<TreeNode*> res;
};

int main(){
    TreeNode *root=new TreeNode(7);
    InsertLeft(root,3);
    InsertRight(root,7);
    InsertLeft(root->right,9);
    InsertRight(root->right,20);
    PrintTree(root); //7 3 7 9 20

    BSTIterator* obj=new BSTIterator(root);
    int firstVal=obj->next();
    cout<<firstVal<<endl; //3
    bool checknext=obj->hasNext();
    cout<<checknext<<endl; //1
    return 0;
}

## C++_ Sol2:

class BSTIterator {
public:
    BSTIterator(TreeNode* root) {
        inorder(root);
    }

    void inorder(TreeNode* root){
        if (root==nullptr)
            return;
        inorder(root->left);
        res.push(root);
        inorder(root->right);
    }

    int next() {
        TreeNode* curRoot=res.front(); res.pop();
        return curRoot->val;
    }

    bool hasNext() {
        return !res.empty() ? true:false;
    }

private:
    queue<TreeNode*> res;
};