Kth Smallest Element in BST — LeetCode 230 Walkthrough

Kth Smallest Element in a BST (#230) is one of the most frequently asked BST problems in coding interviews. It directly tests whether you understand the defining property of a binary search tree — that an inorder traversal visits nodes in sorted ascending order. If you know that single fact, the problem almost solves itself.

The kth smallest element BST leetcode problem asks you to find the kth smallest value in a BST. At first glance, you might think about collecting all values into an array, sorting, and returning the kth element. But that ignores the BST structure entirely. The tree is already sorted — you just need to read it in the right order.

This problem is a gateway to BST Iterator (#173) and other BST traversal problems. Once you master the iterative inorder pattern here, you can adapt it to any scenario where you need sorted access to BST elements without materializing the entire sorted list.

You are given the root of a binary search tree and an integer k. Return the kth smallest value (1-indexed) in the tree. The constraints guarantee that k is always valid — it is between 1 and the number of nodes in the tree.

For example, given the BST [3,1,4,null,2] and k=1, the sorted order of nodes is [1,2,3,4], so the 1st smallest element is 1. For the same tree with k=3, the answer is 3. The key insight is that you never need to fully sort anything — the BST inorder traversal gives you sorted order for free.

This is a Medium problem, but once you see the inorder connection, it is closer to Easy in difficulty. The real interview value is demonstrating that you understand BST properties and can implement an iterative traversal with a stack.

The defining property of a BST is that for every node, all values in the left subtree are smaller and all values in the right subtree are larger. When you perform an inorder traversal (left, node, right), you visit nodes in ascending sorted order. This means the kth node you visit during inorder traversal is the kth smallest element.

You could implement this recursively, traversing the entire tree and collecting values into a list. But that requires O(n) time and O(n) space regardless of k. If k=1, you are doing a full traversal just to return the minimum — wasteful.

The iterative approach with an explicit stack is preferred because it lets you stop the moment you have visited k nodes. You push nodes onto the stack as you go left, pop to visit, then move right. Each pop is one node in sorted order. When your count reaches k, you return immediately.

The iterative inorder traversal uses a stack to simulate the call stack of a recursive solution. You start at the root and push every left child onto the stack until you reach a null. Then you pop the top node — that is the next node in sorted order. After visiting it, you move to its right child and repeat the process.

For the kth smallest element BST leetcode problem, you add a counter. Every time you pop a node from the stack, increment your count. When the count equals k, that node holds the answer. You return immediately without processing the rest of the tree.

The time complexity is O(H + k) where H is the height of the tree. You spend O(H) going down the leftmost path initially, then O(k) pops to reach the kth element. The space complexity is O(H) for the stack, which holds at most one root-to-leaf path at a time.

Consider the BST [3,1,4,null,2] with k=1. The tree looks like this: 3 is the root, 1 is the left child, 4 is the right child, and 2 is the right child of 1. The sorted order is [1,2,3,4], so we need the 1st smallest, which is 1.

Start with current=3. Push 3, move left to 1. Push 1, move left to null. Now pop 1 — that is the 1st element in sorted order. Since k=1, we return 1 immediately. We never even visit nodes 2, 3, or 4.

This demonstrates the power of early termination. In a balanced BST with a million nodes, finding the 1st smallest only requires traversing down the leftmost path (about 20 nodes) and one pop. The iterative approach shines when k is small relative to n.

When k=1, you want the minimum element in the BST. The iterative approach naturally handles this — you go all the way left and pop once. No special case needed.

When k equals the total number of nodes, you want the maximum element. The iterative inorder will traverse the entire tree, visiting every node, and the last pop gives you the max. The time complexity in this case is O(n), which is unavoidable since you need to visit every node.

For a single-node tree, k must be 1 (guaranteed by constraints). You push the root, pop it, and return its value. The stack never holds more than one element.

Kth Smallest in BST is fundamentally about one insight: BST inorder traversal equals sorted order. This single property unlocks an entire family of BST problems. Once you internalize it, problems like Validate BST (#98), BST Iterator (#173), and Inorder Successor (#285) become straightforward.

The iterative inorder pattern with a stack is a technique worth memorizing. It appears in any problem where you need to process BST nodes in sorted order but want the flexibility to stop early, skip nodes, or maintain external state that a recursive approach makes awkward.

If you found this walkthrough helpful, use YeetCode to drill BST traversal patterns with spaced repetition. The kth smallest element BST leetcode problem is a perfect flashcard candidate — the pattern is simple but easy to forget under interview pressure.