Kth Smallest Solution

Iterative inorder, counting as you go:

def kthSmallest(root, k):
    stack = []
    current = root
    while True:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        k -= 1
        if k == 0:
            return current.val
        current = current.right

Time: $O(h + k)$. You descend to the leftmost node ($O(h)$), then visit $k$ nodes.

Space: $O(h)$ for the stack.

For the follow-up: augment each node with the size of its left subtree. Then you can find the kth smallest in $O(h)$ time by comparing $k$ with subtree sizes.