Kth Smallest Element in a BST: in-order traversal as a sorted stream

A binary search tree already encodes sorted order. That sounds like a throwaway observation, but it's the entire problem. The left subtree of any node holds only values smaller than that node; the right subtree holds only values larger. If you visit a BST left-root-right — in-order traversal — the nodes arrive in non-decreasing order. Every single one, guaranteed by the BST invariant. Finding the kth smallest element is then just a matter of counting as you walk and stopping when you reach k.

The real question is whether you exploit that sorted order or ignore it.

What the constraints force

1 <= k <= n <= 10^4 with 0 <= Node.val <= 10^4. The k-validity guarantee (k <= n) means you never have to handle "k is out of range" — the problem promises k always lands on a real node. The upper bound of 10^4 nodes means O(n log n) is perfectly acceptable on a timing basis, but O(n) is achievable without any extra machinery, so there's no reason to settle for worse.

The tree below is example 2: root = [5,3,6,2,4,null,null,1], k=3.

In-order visits: 1, 2, 3, 4, 5, 6. The third node visited is 3. Output: 3.

Brute force: collect everything, sort, index

The most direct approach ignores the BST structure entirely. Traverse the tree in any order — preorder, postorder, doesn't matter — collect all node values into an array, sort it, return values[k-1].

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        values = []
 
        def collect(node):
            if not node:
                return
            values.append(node.val)
            collect(node.left)
            collect(node.right)
 
        collect(root)
        values.sort()
        return values[k - 1]

public class Solution {
    public int KthSmallest(TreeNode root, int k) {
        var values = new List<int>();
        Collect(root, values);
        values.Sort();
        return values[k - 1];
    }
 
    private void Collect(TreeNode node, List<int> values) {
        if (node == null) return;
        values.Add(node.val);
        Collect(node.left, values);
        Collect(node.right, values);
    }
}

Time: O(n log n) — the traversal is O(n), the sort is O(n log n). Space: O(n) to hold the values array plus O(h) for the call stack, where h is tree height.

It works. It's correct. But it discards the single most useful fact about the input: the BST invariant already gives you the sorted order for free. Sorting a collection that's already implicitly sorted is waste.

Recursive in-order with early termination

In-order traversal visits left subtree, current node, right subtree. On a BST, "left subtree then current node then right subtree" means "all smaller values, then this value, then all larger values." Run that recursively from the root and the nodes arrive sorted.

The early-termination part is what makes this better than brute force. Once count reaches k, you've found the answer and you never need to visit another node. For small k on a large balanced tree — say k=1 on a tree with 10^4 nodes — you stop after visiting O(log n) nodes on the path down the left spine, then one more. No reason to touch the other 9999.

Walk through example 2 step by step. The call tree descends left from 5 to 3 to 2 to 1. Node 1 has no left child, so we process it first: count becomes 1. Back to node 2: count becomes 2. Back to node 3 — left subtree done, process node 3: count becomes 3, which equals k. Store result, return immediately. The right subtrees of 3 and 5, plus node 6, are never visited.

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.count = 0
        self.result = 0
 
        def inorder(node):
            if not node or self.count >= k:
                return
            inorder(node.left)
            self.count += 1
            if self.count == k:
                self.result = node.val
                return
            inorder(node.right)
 
        inorder(root)
        return self.result

public class Solution {
    private int _count = 0;
    private int _result = 0;
 
    public int KthSmallest(TreeNode root, int k) {
        _count = 0;
        _result = 0;
        InOrder(root, k);
        return _result;
    }
 
    private void InOrder(TreeNode node, int k) {
        if (node == null || _count >= k) return;
        InOrder(node.left, k);
        _count++;
        if (_count == k) {
            _result = node.val;
            return;
        }
        InOrder(node.right, k);
    }
}

Time: O(h + k) where h is tree height. On a balanced tree that's O(log n + k); on a completely skewed tree (every node only has a right child) it degrades to O(n). Space: O(h) for the recursion stack — O(log n) balanced, O(n) worst case.

The guard self.count >= k at the top of inorder is the early termination. Without it the recursion continues into right subtrees after the answer was already found. Both sides of each node's inorder call check this condition, so the moment count hits k the entire recursion collapses gracefully.

Iterative in-order: same logic, explicit stack

The iterative version replicates the recursive call stack manually using a Python list or C# Stack<T>. The logic is identical — go as far left as possible, process the current node, move right — but the control flow is an explicit loop instead of recursive calls.

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        current = root
        count = 0
 
        while stack or current:
            while current:
                stack.append(current)
                current = current.left
            current = stack.pop()
            count += 1
            if count == k:
                return current.val
            current = current.right
 
        return -1  # unreachable with valid input

public class Solution {
    public int KthSmallest(TreeNode root, int k) {
        var stack = new Stack<TreeNode>();
        var current = root;
        int count = 0;
 
        while (stack.Count > 0 || current != null) {
            while (current != null) {
                stack.Push(current);
                current = current.left;
            }
            current = stack.Pop();
            count++;
            if (count == k) return current.val;
            current = current.right;
        }
 
        return -1; // unreachable with valid input
    }
}

The inner while current loop descends to the leftmost unvisited node and pushes everything along the way onto the stack. When that loop ends, stack.pop() hands you the next node in in-order — you process it, increment count, and then shift to its right child (which becomes the new current for the next outer-loop iteration).

Time and space are the same as the recursive version — O(h + k) time, O(h) stack space — because the explicit stack holds exactly what the call stack held in the recursive version.

Edge cases

k=1 (smallest element). The algorithm descends the entire left spine to the minimum node and stops immediately on the first count == k check. No issue.

k=n (largest element). In-order traversal visits every node; on the nth visit count hits k and returns. This is the worst case for early termination — you pay the full O(n) traversal cost. That's also exactly what brute force costs (minus the sort), so neither approach has an edge here.

Tree with one node, k=1. Root has no left child. The inner descent skips immediately, processes root, count=1=k, returns root.val. Correct.

Completely left-skewed tree (a linked list going left). h=n. Both the recursive and iterative approaches use O(n) stack space. No correctness issue, but this is the degenerate case where the "BST" is indistinguishable from a sorted linked list. In production with n=10^4 this is fine; at n=10^5 you'd start worrying about Python's default recursion limit (typically 1000). The iterative version handles that without issue.

All values identical. The BST invariant allows duplicates at the left child (depending on implementation). In-order still visits them in left-root-right order; the kth visit still returns after k increments. Correct.

Complexity comparison

The follow-up: frequent queries on a mutable BST

The problem asks what you'd do if the BST is modified often — inserts and deletes — and kthSmallest is called frequently. The answer is augmenting each node with the size of its subtree.

Every node stores an extra field: size = 1 + left.size + right.size (leaf nodes have size 1). When you insert or delete, you update the size fields up the path to the root. With that information, kthSmallest becomes a binary search on subtree sizes:

• If k <= left.size, the answer is in the left subtree — recurse left with the same k.
• If k == left.size + 1, the current node is the kth smallest — return it.
• Otherwise, the answer is in the right subtree — recurse right with k - left.size - 1.

class TreeNodeWithSize:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        self.size = 1
 
class AugmentedSolution:
    def kthSmallest(self, root: TreeNodeWithSize, k: int) -> int:
        left_size = root.left.size if root.left else 0
        if k <= left_size:
            return self.kthSmallest(root.left, k)
        elif k == left_size + 1:
            return root.val
        else:
            return self.kthSmallest(root.right, k - left_size - 1)

This brings the query down to O(h) — no longer O(h + k). On a balanced BST that's O(log n) per query. Inserts and deletes still cost O(h) because you update size on the way back up. If the BST is self-balancing (AVL, red-black), both operations land at O(log n).

I'd ship the augmented version the moment "frequent queries" appears in the requirements. The overhead per insert/delete is one extra integer update per node on the path — negligible — and the query speedup is significant for large k on deep trees.

Which version to actually use

For a single query on a static tree, recursive in-order is my first choice. It's shorter, the early-termination logic is obvious, and stack overflow is not a real concern at n=10^4. I'd switch to the iterative version only if the language imposes a tight recursion limit and the tree is skewed.

For repeated queries on a tree that changes, augment the node structure. The in-order approach becomes unnecessarily expensive when called hundreds of times — each call does O(h + k) work that the size field would reduce to O(h).

Brute force is fine for prototyping or for contexts where you have the values already collected for another reason. Not something I'd commit.

Series context and sibling problems

In the trees series, earlier problems (invert binary tree, maximum depth, same tree) established the basic recursive tree-walking pattern. Level-order traversal introduced BFS. This problem is the first one where the type of BST — not just a generic binary tree — changes the algorithm. In-order on a random binary tree gives you nothing useful; on a BST it hands you the values sorted.

Problems with the same shape: LeetCode 94 (binary tree inorder traversal) is the foundation — practice that first if in-order traversal feels unfamiliar. LeetCode 98 (validate BST) also exploits in-order, checking that the sequence is strictly increasing. LeetCode 173 (BST iterator) is essentially the iterative in-order approach packaged as a class with next() and hasNext() methods — the explicit-stack version from approach 3 maps directly onto that design. LeetCode 285 (inorder successor in BST) asks for the next node in in-order order, which is a slight extension: instead of counting to k you walk until you find the next larger value.