Kth Smallest Element in a BST

1. The obvious way

   Collect all values, sort them, take the k-th: O(n log n).

2. The key insight

   An in-order walk of a BST is already sorted. Do it with a stack so you can stop early: dive left as far as possible pushing nodes, pop one (that is the next smallest), count it, then move to its right child and dive left again. The k-th pop is the answer.

3. The algorithm
   1. Stack empty; current = root; counter = 0.
   2. Go as far left as possible, pushing every node on the way.
   3. Pop a node: counter + 1. Counter equals k? That node's value is the answer.
   4. Otherwise move to the popped node's right child and repeat.

Watch it run

stack: 5, 3, 2, 1

def kth_smallest(root, k):
    stack = []
    node = root
    while stack or node:
        while node:                       # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()                # the next smallest value
        k -= 1
        if k == 0:
            return node.val
        node = node.right

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.