Kth Smallest Element in a BST

Interview Prep

StandardTrees Variation of Validate Binary Search Treetreesinorder

The problem

Given the root of a binary search tree and an integer k ≥ 1, return the k-th smallest value in the tree. 

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        self.size = 1   # only needed for the followup

Pattern: in-order, stop on k-th visit

A BST's in-order traversal yields values in sorted order. So the k-th smallest is the k-th value emitted by an in-order walk. The iterative version uses an explicit stack and lets us short-circuit as soon as the counter hits zero — visiting O(h + k) nodes instead of the full O(n).

Iterative solution

def kth_smallest(root: Node, k: int) -> int:
    """In-order traversal. Stop on the k-th visit."""
    stack = []
    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

Recursive (for clarity)

def kth_smallest_recursive(root, k):
    out = []
    def walk(n):
        if n is None or len(out) >= k: return
        walk(n.left)
        if len(out) < k: out.append(n.val)
        walk(n.right)
    walk(root)
    return out[-1]

Trace

Tree:        5
            / \
           3   6
          / \
         2   4
        /
       1

In-order order: 1, 2, 3, 4, 5, 6.
k=3 -> answer 3.

Iterative walk (stack):
  push 5, push 3, push 2, push 1.  pop 1 -> visit (k=2).  go right (None).
  pop 2 -> visit (k=1).  go right (None).
  pop 3 -> visit (k=0).  return 3.

Complexity

Follow-up: many queries on a frequently-modified BST

Interviewers love this follow-up: "what if the BST gets inserts and deletes, and we need many k-th-smallest queries?". The answer is to augment each node with the size of its subtree. With sizes maintained on insert/delete (one extra increment per affected node), the k-th smallest can be found in O(h) — descending left when k falls inside the left subtree, descending right (with k −= left_size + 1) otherwise. 

def kth_smallest_augmented(root: Node, k: int) -> int:
    """If each node knows its subtree SIZE, k-th smallest is O(h) — log n on a balanced BST.
    For repeated queries on a BST that's being mutated, this is the right structure.
    """
    while root:
        left_size = root.left.size if root.left else 0
        if k == left_size + 1:
            return root.val
        if k <= left_size:
            root = root.left
        else:
            k -= left_size + 1
            root = root.right

Why augmentation pays off

Without augmentation, an insert is O(log n) but a k-th-smallest query is O(h + k) — slow when k is large. With augmentation, both are O(log n) on a balanced BST, and the size maintenance is essentially free (one increment per node touched during insert). This is the canonical example of an order-statistics tree.

Variations worth seeing