> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/iii.-binary-tree/173.-binary-search-tree-iterator.md).

# 173. Binary Search Tree Iterator

\# Medium

{% hint style="success" %}
Use interative instead of recursive to do inorder traversal by stack.
{% endhint %}

![](https://3288217904-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LxJcc9A1TOyn5a5HJQ4%2F-M7dTCQd5w1TXMgdvuXy%2F-M7dfmY8kdxIa8sffrRo%2F1589837228148.jpg?alt=media\&token=2bc97b3f-213c-4e91-b541-18739289cbf7)

### Solution:

> If binary tree is a valid binary tree, left subtree is bigger than root, right subtree is bigger than root. Inorder traversal of this binary tree is ascending order.

1. Start from root, push all left nodes to stack. `[7, 3, 1]`
2. Pop out one node from stack, declare `node.right` as new root, then add all left nodes of that new root to stack.
3. stack = `[7, 3, 2]`    result = `[1]`
4. stack = `[7, 3]`          result = `[1,2]`
5. stack = `[7, 5, 4]`    result = `[1,2,3]`
6. stack = `[7, 5]`          result = `[1,2,3,4]`
7. stack = `[7, 6]`          result = `[1,2,3,4,5]`
8. stack = `[7]`                result = `[1,2,3,4,5,6]`
9. stack = `[10, 8]`        result = `[1,2,3,4,5,6,7]`
10. stack = `[10]`              result = `[1,2,3,4,5,6,7,8]`
11. stack = `[12, 11]`     result = `[1,2,3,4,5,6,7,8,10]`
12. stack = `[12]`              result = `[1,2,3,4,5,6,7,8,10,11]`
13. result = `[1,2,3,4,5,6,7,8,10,11,12]`

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

```java
class BSTIterator {
    public List<Integer> res = new ArrayList<Integer>();
    Integer i = -1;
    
    private void inorder(TreeNode root) {
        // stop condition
        if(root == null) return;
        
        inorder(root.left);
        this.res.add(root.val);
        inorder(root.right);
    }
    
    public BSTIterator(TreeNode root) {
        inorder(root);
    }
    
    public int next() {
        this.i ++;
        return this.res.get(i);
    }
    
    public boolean hasNext() {
        if(this.i + 1 < this.res.size())
            return true;
        return false;
    }
}
```

{% endtab %}

{% tab title="Python" %}

```python
class Solution:
    def inorder(self, root, stack):
        if root == None:
            return stack        
        
        while root != None:
            stack.append(root)
            root = root.left      
        
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        result = []
        # add all left nodes of root to stack
        self.inorder(root, stack)
        while len(stack) != 0:            
            root = stack.pop()
            result.append(root.val)
            # if this root has right nodes, add all its left nodes to stack iteratively
            if root.right != None:
                self.inorder(root.right, stack)
                
        return result
```

{% endtab %}
{% endtabs %}