Problem 30 · Trees

Kth Smallest Element in a BST

MediumClassic DSA & systems

01Problem

Given the root of a BST and an integer k, return the kth smallest value (1-indexed).

02Key insight

In-order traversal of a BST yields sorted order; an iterative stack lets you stop after k pops in O(h + k) instead of visiting the whole tree.

03Solution

solution.pypython23 lines

from __future__ import annotations
from dataclasses import dataclass
from typing import Optional

@dataclass
class TreeNode:
    val: int
    left: Optional[TreeNode] = None
    right: Optional[TreeNode] = None

def kth_smallest(root: Optional[TreeNode], k: int) -> int:
    stack: list[TreeNode] = []
    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
    raise ValueError("k exceeds number of nodes")

Try it first.

TimeO(h + k)

SpaceO(h)

tests.py · 2 passing

tests.pypython8 lines

T = TreeNode
root = T(5, T(3, T(2, T(1)), T(4)), T(6))
assert [kth_smallest(root, k) for k in range(1, 7)] == [1, 2, 3, 4, 5, 6]
assert kth_smallest(T(1), 1) == 1
try:
    kth_smallest(T(1), 2); assert False
except ValueError:
    pass

04Staff-level follow-up

Frequent inserts/deletes plus kth queries? Augment each node with its subtree size (order-statistic tree) so kth is O(h) by descending on left-subtree counts.