Walk a BST in sorted order one call at a time. Keep a stack of the left spine; each next() pops a node and pushes its right child's left spine.
▼The problem
LeetCode 173 (Medium). Implement BSTIterator(root) over a binary search tree: next() returns the next smallest value (in-order), hasNext() says whether any values are left.
LeetCode's example: tree [7,3,15,null,null,9,20], calls next, next, hasNext, next, hasNext, next, hasNext, next, hasNext → [null,3,7,true,9,true,15,true,20,false] (the first entry is the constructor). The walkthrough runs it.
The naive way shown: walk the whole tree in order in the constructor and keep every value in a list; next() just reads the list (O(1)), but the list holds all n values even if only one is ever asked for (O(n) memory). The solution shown: an in-order traversal paused between calls, with an explicit stack. The constructor pushes the root's left spine; next() pops the top (the smallest value not yet returned) and pushes the left spine of its right child; hasNext() is "the stack is not empty". Every node is pushed once and popped once, so next() is amortised O(1); the stack holds part of one root-to-node path, so the memory is O(h). It is the same stack walk as ../kth-smallest-in-bst, split into calls. The exact code on screen (CODE in src/scenes/S5.jsx):
class BSTIterator:
def __init__(self, root):
self.stack = []
self.push_left(root)
def push_left(self, node):
while node:
self.stack.append(node)
node = node.left
def next(self):
node = self.stack.pop()
self.push_left(node.right)
return node.val
def hasNext(self):
return len(self.stack) > 0It was checked against the sorted values on 20,000 random BSTs (up to 25 nodes, random hasNext calls between the nexts): the outputs are the sorted values, hasNext is right every time, every node is pushed exactly once and the stack never grows past the tree's height. Every value on screen is computed in code: runIter() in src/deli.jsx runs the same algorithm and records every push, pop and hasNext; the module re-checks it on 400 random BSTs when it loads, and every scene asserts the values it shows (event signatures such as +7 +3 -3 -7 +15 +9 ?T -9 ?T -15 +20 ?T -20 ?F). src/gen_score.py re-runs it (run_iter) and asserts the same signatures for its sound cues.
The solution
class BSTIterator:
def __init__(self, root):
self.stack = []
self.push_left(root)
def push_left(self, node):
while node:
self.stack.append(node)
node = node.left
def next(self):
node = self.stack.pop()
self.push_left(node.right)
return node.val
def hasNext(self):
return len(self.stack) > 0Transcript
Binary Search Tree Iterator. Build an iterator over a search tree: next returns the next smallest value, and has next says whether any are left.
Take seven, with three on its left, and fifteen on its right over nine and twenty. Next gives three, then seven. Has next: true. Then nine, fifteen and twenty, with a true before each. Finally, has next is false.
The easy way: walk the tree in order up front, and save every value in a list. Next just reads it. Quick, but it stores all n values, even if you only ask for one.
The key idea: it's an in-order traversal, paused between calls. Keep a stack of waiting nodes. First, push the left spine: the root, its left child, and on down. The top is always the smallest value not yet returned. To serve it, pop it, then push its right child's left spine.
In code, the constructor pushes the left spine. Next pops the top, pushes its right child's left spine, and returns the value. Has next checks the stack isn't empty.
Now the example. Push seven, then three. Next pops three: no right child. Next pops seven, and pushes fifteen, then nine. Has next: true. Pop nine. True, pop fifteen, which pushes twenty. True, pop twenty. The stack is empty: has next is false.
Every node is pushed once and popped once, so next is constant time on average. The stack holds one path: order h space, not n.
Stack the left spine, pop the smallest, push the right side's spine. That's Binary Search Tree Iterator.