BST Iterator

BST Iterator asks you to walk a binary search tree in sorted order — but lazily, one value per next() call, instead of dumping the whole traversal up front. The trick is to simulate an in-order traversal with an explicit stack so each call is amortized O(1) time and the stack never holds more than the tree height.

The slow way first

The easy approach: do a full in-order traversal in the constructor, dump every value into a list, and let next() hand them out one at a time. That works and next() is O(1) — but it costs O(n) space and O(n) time before the first call, even if the caller only ever wants one or two values. We can do better.

The question to ask: can I produce the next value on demand without precomputing the whole list? In-order traversal is naturally recursive (left, node, right). If we make that recursion explicit with a stack, we can pause it after every node and resume on the next call.

The idea: a stack holding the left spine

An in-order traversal always goes as far left as possible first. So we keep an invariant: the stack always holds the path of nodes whose left subtrees are fully processed but the nodes themselves are not yet yielded — the left spine of the remaining work, with the smallest unseen node on top.

In the constructor, push the left spine of the root. Then next() pops the top (the smallest), and because we just consumed that node, the next-smallest values live in its right subtree — so we push the left spine of the popped node's right child.

The top of the stack is always the next value to return. A node is pushed once and popped once, so across n calls the work is O(n) total — amortized O(1) per next().

Walk through it

Step through the animation. The constructor pushes the spine 5 → 3 → 1, leaving 1 on top. Each next() pops the top, yields it, and — if the popped node has a right child — pushes that child's left spine. Watch the stack shrink on a leaf and grow again when a right subtree appears. The yielded values come out perfectly sorted.

Pseudocode

constructor(root):
    stack = empty
    node = root
    while node is not None:        # push the whole left spine
        stack.push(node)
        node = node.left
 
next():
    node = stack.pop()             # smallest unseen node
    cur = node.right               # next values live to its right
    while cur is not None:         # push the right child's left spine
        stack.push(cur)
        cur = cur.left
    return node.value
 
has_next():
    return stack is not empty

The Python solution

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        node = root
        while node:
            self.stack.append(node)
            node = node.left
 
    def next(self):
        node = self.stack.pop()
        val = node.val
        cur = node.right
        while cur:
            self.stack.append(cur)
            cur = cur.left
        return val
 
    def has_next(self):
        return len(self.stack) > 0

• The constructor walks from the root, pushing each node and stepping left, until there is no left child — that is the left spine.
• In next(), self.stack.pop() removes the top, which is the smallest node not yet returned.
• After popping, the next-smallest values are in node.right, so we push that subtree's left spine with the same while loop.
• If the popped node has no right child, the inner loop does nothing — we simply return and the stack shrinks.
• has_next() is true exactly when the stack still holds nodes.

Complexity

The stack never holds more than the tree height h (the length of one spine), so space is O(h) — far better than the O(n) of precomputing the whole list. For a balanced tree that is O(log n).

When this pattern shows up

Practice