0173.md

173. Binary Search Tree Iterator

Level:

Topic:

Question

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST)

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]\

Explanation

BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // return 3
bSTIterator.next();    // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 20
bSTIterator.hasNext(); // return False

Intuition

Iterative inorder traversal need a stack

Code

Time: O(n)
Space: O(n)

class BSTIterator {
    Stack<TreeNode> stack;
    TreeNode curr;

    public BSTIterator(TreeNode root) {
        this.curr = root;
        this.stack = new Stack<>();
    }

    public int next() {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        int next = curr.val;
        curr = curr.right;
        return next;
    }

    public boolean hasNext() {
        return curr != null || !stack.isEmpty();
    }
}