173. Binary Search Tree Iterator

-
https://leetcode.com/problems/binary-search-tree-iterator/

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.

    Example:
    BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false

    Note:
    • next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
    • You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.
    ---
    Intuition
    Saving in order traversal in array list is trivial

    We can do better to only save leftmost path on stack

    constructor
    stack = new Stack<TreeNode>();
    getLeftMost(root)

    getLeftMost(TreeNode root)
        while (root != null) {
            stack.push(root);
            root = root.left;
        }

    next
        ans = stack.pop()
        if (ans.right != null) {
            getLeftMost(ans.right)
        }
        return ans.val;

    hasNext
        return !stack.isEmpty()
    ---
    Time - O(1) - Amortized for next .. O(N) worst case skewed tree

    Space - O(h) 
    ---