Kth Smallest Element in a BST — LC 230 Iterative Inorder Interview Guide

Problem Statement#

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

Constraints:

• Number of nodes is in range 1 to 10000
• 1 less than or equal to k less than or equal to number of nodes
• Node values fit in 32-bit signed integer range

Input:  root = [3,1,4,null,2], k = 1
Output: 1

Input:  root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

Why This Problem Matters#

LeetCode 230 Kth Smallest Element in a BST is a Medium that appears in Amazon, Meta, Uber, Bloomberg, and Apple interviews. It tests a fundamental BST property — inorder traversal yields nodes in sorted order — and how to combine that with early termination.

The follow-up is the real interview question: "If the BST is modified frequently with insertions and deletions, and you must find the kth smallest often, how would you optimize?" The answer is to augment each node with subtree size and navigate in O(log n) per query. That augmentation pattern (LC 1206 Skip List, order statistic trees) is what senior loops want to hear.

The problem also separates candidates who write iterative tree traversal from those who only know recursion. Iterative inorder with an explicit stack is a high-leverage skill for tree iterators, BST validation, and Morris traversal.

The Core Insight#

Inorder traversal (left, root, right) of a BST visits nodes in increasing value order. To find the kth smallest, perform inorder traversal and stop after popping k nodes — the kth popped node is the answer.

Iterative inorder uses an explicit stack:

1. Walk left as far as possible, pushing every node onto the stack.
2. Pop the top — this is the next node in sorted order.
3. Decrement k. If k reached 0, return the popped value.
4. Set current to the popped node's right child and repeat.

Time complexity is O(h + k): we traverse h nodes to reach the leftmost, then pop k more. Space is O(h) for the stack.

Visual Dry Run#

BST: 5 -> {3 -> {2, 4}, 6}, k = 3.

Wait — k=3 should yield 4. Let me recount: smallest order is 2, 3, 4, 5, 6. The 3rd smallest is 4. Correct.

Solution (Optimal)#

class Solution:
    def kthSmallest(self, root, k):
        stack = []
        curr = root
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            k -= 1
            if k == 0:
                return curr.val
            curr = curr.right
        return -1

var kthSmallest = function(root, k) {
    const stack = [];
    let curr = root;
    while (curr || stack.length > 0) {
        while (curr) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        k -= 1;
        if (k === 0) return curr.val;
        curr = curr.right;
    }
    return -1;
};

Time: O(h + k) — push left spine in O(h), then pop k nodes. Space: O(h) — stack at most holds the leftmost spine.

Common Mistakes#

• Using recursive inorder without early termination — wastes time on nodes after the kth
• Decrementing k before the leftmost dive completes, off-by-one in the count
• Forgetting to set curr = curr.right after a pop, causing an infinite loop on the same node
• Treating k as 0-indexed when the problem is 1-indexed
• Returning curr.val after the inner while-loop, not after the pop and decrement

Interview Tips#

• State explicitly that inorder of a BST is sorted — anchor the rest of the solution to that fact
• Walk through the iterative-inorder template; many candidates only know recursive
• Prepare the augmented-BST follow-up: store subtree size at each node and navigate in O(log n)
• Mention Morris traversal as O(1) space alternative if asked about constant memory

Follow-up Questions#

• Frequent inserts and queries (the canonical follow-up) — augment nodes with size, navigate in O(log n)
• Kth largest — reverse inorder (right, root, left)
• Kth smallest in a stream — maintain a balanced BST or order-statistic tree
• Two trees combined kth smallest — two-pointer on iterators

Key Takeaways#

• LeetCode 230 Kth Smallest Element in a BST is Medium, frequently asked at Amazon, Meta, Uber, and Bloomberg
• Time is O(h + k); space is O(h) for the iterative inorder stack
• Inorder traversal of a BST visits nodes in strictly increasing order — fundamental BST property
• Iterative inorder with explicit stack enables early termination after k pops
• For frequent kth-queries on a mutable BST, augment each node with subtree size for O(log n) lookups
• Reverse inorder (right, root, left) gives kth largest with the same template
• Morris traversal achieves O(1) extra space using temporary thread pointers