Kth Smallest Element in a BST

def kthSmallest(root, k):
    stack, node, count = [], root, 0
    while True:
        while node:                 # slide left
            stack.append(node)
            node = node.left
        node = stack.pop()          # next smallest
        count += 1
        if count == k:
            return node.val
        node = node.right           # step right

K-th Smallest Element in a BST. Given the root of a binary search tree and a number k, return the k-th smallest value in the tree.

Take this tree: three on top, one and four below, and two under one. With k equal to one, the answer is the smallest, one. In this bigger tree, with k equal to three, it's three.

The simple way: collect every value in a list, sort it, and take the one at position k minus one. It works, but it stores all n values and sorts them, even when k is tiny.

But a search tree is already sorted: everything left of a node is smaller, everything right is bigger. So an in-order traversal, left side, then the node, then the right side, visits values from smallest to largest. Count as you go, and stop at the k-th.

In code, keep a stack. Slide left as far as you can, pushing each node. Pop one: that's the next smallest. Count it, and if the count reaches k, return its value. Otherwise, step to its right child and repeat.

Run it with k equal to three. Slide down the left edge, pushing five, three, two and one. Pop one: count one. No right child, so pop two: count two. Pop three: count three. That's k, so the answer is three. Four, five and six are never visited.

The stack holds one path, so the space is the tree's height. The time is the height plus k: one slide down, then k visits.

Go left, count, stop at k. That's K-th Smallest Element in a BST.