BST Iterator
LeetCode 173 • Medium • Trees
Input: root = [7,3,15,null,null,9,20] → next sequence: 3,7,9,15,20
Controlled inorder: keep a left-spine stack. next pops and pushLeft(right).
TimeO(1)*amortized next
SpaceO(h)left-spine stack
Stack: []Yielded: []
Current
In Stack
Yielded
Stack
empty
next()
[]
Ready
Press Play. Init pushLeft(root). Then next() until hasNext is false.