LeetCode Kth Smallest Element in a BST

LeetCode 230 — Kth Smallest Element in a BST — is a one-line problem hiding a two-paragraph follow-up. The one-liner: inorder traversal of a BST visits values in sorted order, so the kth visited node is the answer. The follow-up: “What if the tree is modified often and you need many kth queries?” That is where interviewers separate the rehearsed from the prepared.

The Problem

Given the root of a BST and an integer k, return the kth smallest value in the tree. Assume 1 <= k <= n, where n is the number of nodes.

Brute Force

Flatten the entire tree into a list with any traversal and sort it.

def kthSmallest(root, k):
    vals = []
    def walk(node):
        if not node:
            return
        walk(node.left)
        vals.append(node.val)
        walk(node.right)
    walk(root)
    return vals[k - 1]

This already uses inorder, so the list comes out sorted. But it touches every node even when k is small, and it allocates a list of size n.

Optimal Solution

Run an iterative inorder traversal and stop as soon as you have popped k nodes.

def kthSmallest(root, k):
    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

For small k, this can finish in O(h + k) instead of O(n). Same asymptotic worst case, dramatically better practical behavior.

Walk Through an Example

Use the BST [5, 3, 6, 2, 4, null, null, 1] with k = 3.

• Push 5, then 3, then 2, then 1. Stack: [5, 3, 2, 1]. Node is null.
• Pop 1. k becomes 2. Move right — null.
• Pop 2. k becomes 1. Move right — null.
• Pop 3. k becomes 0. Return 3.

We never touched 4, 5, or 6. The early exit pays off.

Edge Cases

• A skewed tree that is purely left children — the inner while walks all the way down before any pop, so the first iteration is O(h).
• k equals the total number of nodes — we end up traversing the entire tree.
• A tree with a single node and k = 1 — handled by the loop body.
• Duplicates — the standard BST definition forbids them, so the problem is well-defined.

Complexity Analysis

Time is O(h + k), where h is the height. For balanced trees this is O(log n + k), for skewed it is O(n). Space is O(h) for the explicit stack. The brute force is O(n) time and O(n) space regardless of k.

If you reach for recursion, the cost is the same but the call stack is implicit.

How to Explain It in an Interview

Start with the invariant: inorder on a BST yields sorted order. Then make the optimization explicit: you do not have to finish the traversal — pop until k hits zero. Walk through the iterative inorder loop once because it is the kind of code people forget under pressure.

Then volunteer the follow-up before it is asked: “If the BST is modified often and we need many kth queries, augment each node with a count of nodes in its subtree. Then locating the kth smallest becomes a guided walk in O(h).” This single sentence reliably moves the conversation forward.

Related Problems

• LeetCode 98 — Validate Binary Search Tree
• LeetCode 173 — Binary Search Tree Iterator (same iterative-inorder skeleton)
• LeetCode 538 — Convert BST to Greater Tree (reverse inorder)
• LeetCode 270 — Closest BST Value

Many of these reuse the same stack pattern. For more on traversal order intuition, revisit Binary Tree Traversals.

Wrap up

Kth Smallest in a BST is a chance to show three things in one answer: that you know inorder yields sorted order, that you can write iterative tree code cleanly, and that you have thought past the literal prompt to the maintenance-heavy follow-up. The augmented-tree mention is what separates a passing answer from a strong-hire one.

If recursion still feels shaky, the recursion fundamentals post is the right warm-up before drilling this problem.