Why it works
- In a binary search tree, in-order gives the values from smallest to largest, so the k-th value popped is the k-th smallest.
- The stack lets the walk stop in the middle: once k reaches 0 we return, and the nodes still waiting or never reached cost nothing.
Complexity
Time O(h + k), where h is the height of the tree: one path down to the smallest value, then k pops. Memory O(h): the stack holds one path.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗