p18 — Hints

Open one at a time.

Hint 1 — What property of BST gives you “sorted order”?

Inorder traversal of a BST visits nodes in strictly ascending value order. So the k-th node visited (1-indexed) is the k-th smallest. You don’t need a full sort — just walk inorder.

Hint 2 — Don’t Walk the Whole Tree

If you do a full recursive inorder collecting every value into a list, you walk all N nodes even when k=1. Stop as soon as you’ve visited the k-th node. Maintain a counter; return early.

Hint 3 — Iterative Inorder + Counter (the shippable form)

stack, cur = [], root
while cur or stack:
    while cur:
        stack.append(cur); cur = cur.left
    node = stack.pop()
    k -= 1
    if k == 0: return node.val
    cur = node.right

Memorize this template. It reappears in LC 173, 285, 99.

Complexity: O(H) descent + O(k) pops + O(H) stack space = O(H + k) time, O(H) space.

Hint 4 — Pre-Empt the Follow-up

Before you finish, anticipate the interviewer’s next question:

“Suppose the BST is modified often (frequent insert/delete), and we run kth_smallest many times. How do you optimize?”

You have 30 seconds to identify the answer: augment each node with its subtree size.

Hint 5 — Augmented BST (Order-Statistic Tree)

Add a field size to each node, where size(N) = 1 + size(N.left) + size(N.right) (with size(None) = 0).

Maintain size on every insert/delete (recompute after the recursive call returns).

For kth_smallest(node, k):

left_size = size(node.left)
if k <= left_size:        descend left, same k
elif k == left_size + 1:  return node.val
else:                     descend right, k -= left_size + 1

Per query: O(H). Per mutation: O(H) including size maintenance. Combined with self-balancing (AVL/RB), this gives O(log N) per op worst-case.

This is called an order-statistic tree (CLRS Ch. 14). Naming it explicitly in interview signals you’ve read the textbook.