Binary Search Tree Iterator

Design an iterator over a binary search tree with the following rules:

• Elements are visited in ascending order (i.e. an in-order traversal)
• next() and hasNext() queries run in O(1) time in average.

Challenge:

Extra memory usage O(h), h is the height of the tree.

Super Star: Extra memory usage O(1)

Solution:

Simple implementation will be decompose in-order traversal into two functions.

Code:

public class BSTIterator {
    private Stack<TreeNode> stack = new Stack<>();
    private TreeNode cur;
    public BSTIterator(TreeNode root) {
        cur = root;
    }

    //@return: True if there has next node, or false
    public boolean hasNext() {
        return cur != null || !stack.empty();
    }

    //@return: return next node
    public TreeNode next() {
        if (!hasNext()) {
            return null;
        }
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode node = stack.pop();
        cur = node.right;
        return node;
    }
}