173. Binary Search Tree Iterator

# Medium

Use interative instead of recursive to do inorder traversal by stack.

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]

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

Python