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
    2

To put this in plain English: you are given a binary search tree. If you were to list out all the numbers in the tree from smallest to largest, which number would be exactly at the k-th position? (1-indexed, so k=1 is the smallest).

Constraints to Keep in Mind:

• 1 <= k <= Number of nodes in the tree <= 10^4
• 0 <= Node.val <= 10^4
• The tree can be heavily unbalanced.

The Brute Force Approach

The simplest way is to collect all the values into an array, sort the array, and grab the k-1 index.

• How it works: You run any traversal (preorder, postorder, etc.), append every node's value to a list, call .sort() on the list, and return list[k-1].
• Why it's too slow: Sorting takes O(n \log n) time, and storing all elements takes O(n) space. Even if you use an in-order traversal to skip the sorting step (since in-order on a BST yields sorted values automatically), building the full array still takes O(n) time and O(n) space. We don't want to process all n nodes if k is small. We want to stop exactly when we hit the k-th node.

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;
}

Code Walkthrough (Iterative In-order)

1. stack = [], node = root: Initialize a stack to keep track of nodes we need to return to, and start at the root.
2. while stack or node:: Continue as long as there are unvisited nodes or nodes waiting in the stack.
3. while node:: Dive as far left as possible. We want the absolute smallest element first, which lives at the bottom-left.
4. stack.append(node), node = node.left: Push nodes onto the stack as we pass them so we remember to visit them later.
5. node = stack.pop(): Once we hit a dead end (null left child), pop the last node from the stack. This node is guaranteed to be the next smallest available number.
6. k -= 1: We found one! Decrement our counter.
7. if k == 0: return node.val: If this was the k-th node we've popped, we're done. Return it immediately.
8. node = node.right: After visiting a node, we must explore its right subtree to find numbers slightly larger than it.

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.

Hand Trace

Trace on the example tree:

     3
   / \
  1   4
   \
    2

Find k = 3.

• Start: node = 3, stack = [].
• Dive left: push 3, node = 1. push 1, node = null. stack = [3, 1].
• Pop 1: node = 1. k becomes 2. Next node = 1.right = 2. stack = [3].
• Dive left: push 2, node = null. stack = [3, 2].
• Pop 2: node = 2. k becomes 1. Next node = 2.right = null. stack = [3].
• Dive left: node = null, loop skipped.
• Pop 3: node = 3. k becomes 0. Target found!
• Return 3. ✓

Order of pops: 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

• Time Complexity: O(h + k). To find the first (smallest) element, we must traverse down to the leftmost leaf, which takes O(h) steps where h is the tree's height. Then we pop and process k nodes. So total time is proportional to h + k. If the tree is balanced, h \approx \log n. If k is small, this is highly efficient. If k \approx n, it degrades to O(n).
• Space Complexity: O(h). The maximum size of the stack at any given time is the length of a single path from the root down to a leaf, which is the height of the tree h. No additional space is needed.

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.