02
Intuition
Inorder traversal of a BST emits values in sorted order — so the k-th visited node is the answer. Traverse iteratively and stop early; no need to materialize the whole list.
03
Approach
1
Inorder = sorted stream
Left, node, right yields ascending values by the BST property.
2
Iterate with an explicit stack
Push the left spine; pop = next smallest; then walk the popped node's right subtree's left spine.
3
Stop at k
Decrement k per pop; return when it hits zero — O(h + k) work.
04
Solution & live demo
python
▶1class Solution:
▶2 def kthSmallest(self, root, k):
▶3 stack = []
▶4 node = root
▶5 while True:
▶6 while node:
▶7 stack.append(node)
▶8 node = node.left
▶9 node = stack.pop()
▶10 k -= 1
▶11 if k == 0: return node.val
▶12 node = node.right
05
Edge cases
k = tree size
Traversal ends exactly on the maximum node.
Frequent queries with inserts
Augment nodes with subtree sizes → O(h) per query (LeetCode's follow-up).
06
Complexity
Time
O(h + k)
Space
O(h)
Early-stopping iterative inorder.