Why it works
- The stack holds exactly the nodes in-order still owes: each one waits below the nodes of its left subtree, so the top is always the smallest value not given yet.
- After next() pops a node, the values right after it are in its right subtree, smallest first down its left side; pushLeft puts them on top, above the node's ancestors that come later.
- Every node is pushed and popped once over all calls, so next() is O(1) on average even when one call pushes a whole path.
Complexity
Time O(1) on average per call: n pushes and n pops spread over n calls of next(); hasNext() is O(1). Memory O(h): the stack holds at most one path from the root.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗