4.14.12 — Kth Smallest Element in a BST

LeetCode 230 · Medium · ★ Blind 75

The problem

Return the k-th smallest value in a binary search tree, counting from 1.

     3
   / \
  1   4        k = 1  →  1
   \
    2

The pattern

One fact does all the work:

An in-order traversal of a binary search tree visits the values in increasing order.

Left subtree, then the node, then the right subtree. Because everything on the left is smaller and everything on the right is larger, that order is sorted by construction.

So the k-th smallest is simply the k-th node visited in order. Walk in order, count, and stop at k.

The stopping matters. Collecting every value into a list and indexing works and is O(n) time and space; stopping early makes it O(h + k), which is much better when k is small.

The solution

Python

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        node = root

        while stack or node:
            while node:                 # go as far left as possible
                stack.append(node)
                node = node.left

            node = stack.pop()          # this is the next value in order
            k -= 1
            if k == 0:
                return node.val

            node = node.right           # then explore its right subtree

TypeScript

function kthSmallest(root: TreeNode | null, k: number): number {
  const stack: TreeNode[] = [];
  let node = root;

  while (stack.length || node) {
    while (node) {
      stack.push(node);
      node = node.left;
    }

    node = stack.pop()!;
    if (--k === 0) return node.val;

    node = node.right;
  }

  return -1;
}

The iterative in-order walk is worth learning as a shape, because it is the only traversal where the iterative version is genuinely useful — it lets you stop mid-walk, which recursion cannot do cleanly.

Read it as three steps repeating:

1. Dive left, pushing every node you pass. The stack now holds the chain of ancestors you will come back to.
2. Pop. That node is next in sorted order, because everything smaller than it has already been visited.
3. Turn right and repeat, which handles its right subtree before returning to the ancestors on the stack.

The stack is doing exactly what the call stack would do in the recursive version — holding the nodes you still owe a visit to.

Trace

     3
   / \
  1   4
   \
    2

Dive left from 3: push 3, push 1. Pop 1 → first value. Turn right to 2, dive: push 2. Pop 2 → second value. No right child. Pop 3 → third value. Turn right to 4, push 4. Pop 4 → fourth.

Order: 1, 2, 3, 4. Sorted. ✓

The recursive version

def kthSmallest(self, root, k):
    self.k = k
    self.answer = None

    def inorder(node):
        if not node or self.answer is not None:
            return
        inorder(node.left)
        self.k -= 1
        if self.k == 0:
            self.answer = node.val
            return
        inorder(node.right)

    inorder(root)
    return self.answer

Shorter, but the early exit needs a guard at the top of every call, because a return only leaves one frame. That awkwardness is exactly why the iterative version is preferred here.

Complexity

O(h + k) time — dive to the leftmost node, then pop k times. For a balanced tree with small k that is close to O(\log n).

O(h) space for the stack.

The follow-up that matters

"What if the tree is modified often and you need this frequently?"

Walking the tree for every query is O(h + k) each time, which is wasteful when queries are common. The answer is to augment the tree: store in each node the size of its subtree.

Then finding the k-th smallest becomes a single root-to-leaf walk:

let L = size of the left subtree
if k <= L        → the answer is in the left subtree
if k == L + 1    → this node is the answer
otherwise        → go right, looking for the (k − L − 1)-th

That is O(h) per query, with no dependence on k at all. The cost is maintaining the sizes on insertion and deletion, which is O(h) per update, since only the nodes along one path change.

This is a genuinely important idea: storing an aggregate in each node so that queries become walks. It is how order-statistic trees work, and it is the same technique behind segment trees and Fenwick trees in 4.13.4.

Where this goes next

• Kth Largest Element in a BST — reverse in-order: right, node, left.
• Range Sum of BST — prune whole subtrees that fall outside the range, using the ordering.
• BST Iterator (LeetCode 173) — this exact stack, exposed as next() and hasNext(). It is O(1) amortized per call and O(h) space, which is the same argument as the monotonic stack in 4.8: each node is pushed once and popped once.

What the interviewer will push on

"Why does in-order give sorted output?" Left is smaller, right is larger, so visiting left–node–right is sorted by construction.

"Why iterative rather than recursive?" Stopping early is clean; with recursion you need a guard in every frame.

"What if the tree changes often?" Augment nodes with subtree sizes for O(h) queries.

"What if you needed the k-th largest?" Reverse the traversal.

One thing to volunteer: say the in-order fact out loud before writing anything, and note that you will stop at k rather than collect everything.

Next: 4.14.13 Construct Binary Tree from Preorder and Inorder — going backwards, from traversals to the tree.