Inorder traversal of a BST visits nodes in sorted order.
Think about why: inorder visits left subtree first (all smaller values), then current node, then right subtree (all larger values). Recursively, this produces sorted output.
This property is powerful:
- To find the -th smallest element, do inorder and stop at the -th node
- To find successor/predecessor, traverse in order
- To check if a tree is a valid BST, check if inorder is sorted
# k-th smallest
def kthSmallest(root, k):
stack = []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
k -= 1
if k == 0:
return current.val
current = current.right