Kth Smallest Element in a BST

How you get there

1. 1In-order traversal of a BST yields ascending values.
2. 2An iterative traversal with an explicit stack can stop as soon as k values are seen.
3. 3That gives O(h + k) rather than traversing the whole tree.

Solution

def kth_smallest(root, k: int) -> int:
    stack: list = []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right
    return -1

Time

O(h + k)

Space

O(h)

What goes wrong

A recursive traversal collecting everything into a list works but cannot stop early.