Kth Smallest in a BST

Signal

"Kth smallest / order statistic in a BST" — an in-order traversal of a BST visits values in ascending order for free, so the answer is just "stop at the k-th value visited." No sorting, no auxiliary array required.

Approach

Do an in-order traversal (left, node, right) with an explicit counter. The moment the counter reaches k, that node's value is the answer. Use an iterative traversal with a stack so you can stop the instant you find it, instead of building the full sorted list first.

Skeleton

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

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def kth_smallest(root: TreeNode | None, k: int) -> int:
    stack: list[TreeNode] = []
    node = root
    count = 0

    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        count += 1
        if count == k:
            return node.val
        node = node.right

    raise ValueError("k is out of range for this tree")

Complexity

O(h + k) time — descend to the leftmost node once (O(h)), then k pops. O(h) space for the stack. Worst case O(n) if k is close to n or the tree is skewed.

Pitfalls

• Recursively collecting the full in-order list, then indexing result[k-1], works but costs O(n) time and space even when k is small — the iterative stack version stops as soon as it finds the answer.
• k is 1-indexed — the first node popped is the 1st smallest, not the 0th.