BST Iterator
Iterator over a BST's inorder sequence: next() and hasNext() in amortized O(1), O(h) memory.
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.
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
python
▶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
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.
06
Complexity
Time
amortized O(1)
Space
O(h)
Each node pushed once over the whole iteration.