The problem. Implement a class BSTIterator over the in-order walk of a binary search tree: the constructor takes the root, next() returns the next smallest value, and hasNext() says whether any are left. The follow-up asks for next() and hasNext() in O(1) amortized time with O(h) memory.
BSTIterator it = new BSTIterator([7, 3, 15, null, null, 9, 20])
it.next() -> 3
it.next() -> 7
it.hasNext() -> true
it.next() -> 9
it.next() -> 15
it.next() -> 20
it.hasNext() -> falseDo the whole in-order walk up front into a list, then hand values out with an index.
class BSTIterator { constructor(root) { this.values = []; this.i = 0; const inorder = (node) => { if (node === null) return; inorder(node.left); this.values.push(node.val); inorder(node.right); }; inorder(root); } next() { return this.values[this.i++]; } hasNext() { return this.i < this.values.length; }}O(n) constructor, O(1) next and hasNext, O(n) memory. Fast, but it fails the memory follow-up — and it does all the work even if the caller only wants the first value.
Unroll the iterative in-order walk and pause it between values. The stack holds the nodes whose left side is done but which haven't been returned yet. next() pops the top (the smallest left), then pushes the left spine of its right child.
next() pops the smallest pending node, then pushes the left spine of its right child.
class BSTIterator { constructor(root) { this.stack = []; this.pushLeft(root); } pushLeft(node) { // the node and its whole left spine while (node !== null) { this.stack.push(node); node = node.left; } } next() { const node = this.stack.pop(); // the smallest value not yet returned this.pushLeft(node.right); // its right subtree comes next return node.val; } hasNext() { return this.stack.length > 0; }}O(h) memory, O(1) amortized time. One next() may push a long spine, but every node is pushed once and popped once over the whole iteration — n pushes spread over n calls.
