LeetCode #173 Hard

BST Iterator

Iterator over a BST's inorder sequence: next() and hasNext() in amortized O(1), O(h) memory.

bststackdesign

02

Intuition

Pause an inorder traversal mid-flight: keep only the stack of ancestors-to-revisit (the left spine). next() pops one node and pushes the left spine of its right subtree. Each node is pushed and popped exactly once, so n calls cost O(n) total.

How to spot this pattern

A paused inorder traversal. The stack holds exactly the left spine — the nodes whose values are still pending — so next() pops one and pushes the spine of its right child. Space is O(h), not O(n), because only one root-to-node path is ever stored.

03

Approach

1

Left spine = frozen traversal state

The stack holds exactly the nodes whose left sides are done but who themselves aren't emitted.

2

next()

Pop the top (the current smallest remaining), then walk its right child's left spine onto the stack.

3

hasNext()

Stack non-empty. Memory never exceeds the tree height.

04

Solution & live demo

▶1class BSTIterator:
▶2    def __init__(self, root):
▶3        self.stack = []
▶4        self._spine(root)
▶5 
▶6    def _spine(self, node):
▶7        while node:
▶8            self.stack.append(node)
▶9            node = node.left
▶10 
▶11    def next(self):
▶12        node = self.stack.pop()
▶13        self._spine(node.right)
▶14        return node.val
▶15 
▶16    def hasNext(self):
▶17        return bool(self.stack)

05

Common pitfalls

Flattening the whole tree in the constructor

✗ Wrong

self.vals = inorder(root)
self.i = 0

✓ Right

self.stack = []
self._spine(root)

Correct and often accepted, but it's O(n) memory and does all the work up front. The stack version uses O(h) and amortises the traversal across the calls that actually happen.

Pushing the right child rather than its spine

✗ Wrong

if node.right:
    self.stack.append(node.right)

✓ Right

self._spine(node.right)

The right child's own left descendants come before it in inorder. Pushing just the child returns it too early, emitting values out of order.

Descending right in the initial spine

✗ Wrong

while node:
    self.stack.append(node)
    node = node.right

✓ Right

while node:
    self.stack.append(node)
    node = node.left

Inorder starts at the leftmost node. Following right pointers seeds the stack with the largest values, so the iterator returns the tree in roughly reverse order.

06

Edge cases

Right-skewed tree

Stack holds one node at a time; each next() pushes the next chain node.

Calls after exhaustion

hasNext() false guards; next() on empty is undefined by contract.

07

Complexity

Time

amortized O(1)

Space

O(h)

Each node pushed once over the whole iteration.